I teorien om algoritmer er kompleksitetsklasser sæt af beregningsmæssige problemer, der er omtrent det samme med hensyn til beregningsmæssig kompleksitet. Mere snævert er kompleksitetsklasser sæt af prædikater ( funktioner , der tager et ord som input og returnerer et svar på 0 eller 1), der bruger omtrent den samme mængde ressourcer til at beregne.
For hver klasse er der en kategori af opgaver, der er "sværeste" i den klasse. Det betyder, at enhver opgave fra en klasse reduceres til sådan en opgave, og desuden ligger selve opgaven i klassen. Sådanne opgaver kaldes komplette opgaver ( eng. -complete ) for en given klasse. Det bedst kendte komplette problem er NP-komplet problem .
Komplette problemer er et praktisk værktøj til at bevise klasselighed. Det er nok for et sådant problem at give en algoritme, der løser det og tilhører en mindre klasse, og ligheden vil blive bevist.
Hver kompleksitetsklasse (i snæver forstand) er defineret som et sæt prædikater, der har bestemte egenskaber. En typisk definition af en kompleksitetsklasse ser sådan ud:
En kompleksitetsklasse X er et sæt prædikater P(x) , der kan beregnes på Turing-maskiner og bruger en O (f(n)) ressource til at beregne, hvor n er længden af ordet x .Ressourcerne tages normalt som beregningstid (antallet af arbejdscyklusser for Turing-maskinen) eller arbejdsområdet (antallet af celler, der bruges på båndet under drift). Sprog, der genkendes af prædikater fra en bestemt klasse (det vil sige det sæt af ord, som prædikatet returnerer 1 for) siges også at tilhøre samme klasse.
Derudover kan mange klasser også beskrives i form af matematisk logik eller spilteori .
Klasser er normalt angivet med store bogstaver. Komplementet til klasse C (det vil sige klassen af sprog, hvis komplementer hører til C ) betegnes co-C .
Alle kompleksitetsklasser er i et hierarkisk forhold: nogle inkluderer andre. For de fleste inklusioner vides det dog ikke, om de er strenge. Et af de mest berømte åbne problemer på dette område er ligestillingen af klasserne P og NP . Hvis denne antagelse er korrekt (hvilket mange videnskabsmænd tvivler på), så vil klassehierarkiet vist til højre være stærkt kollapset. I øjeblikket er den mest almindelige hypotese , at hierarkiet er ikke-degenereret (det vil sige, at alle klasser er forskellige). Derudover er det kendt med sikkerhed, at EXPSPACE ikke er lig med PSPACE-klassen .
Overvej en funktion f og en inputstreng med længden n . Derefter defineres klassen DTIME (f(n)) som klassen af sprog, der accepteres af deterministiske Turing-maskiner , der afslutter deres arbejde i tid, der ikke overstiger f(n) . Klassen NTIME (f(n)) er på sin side defineret som klassen af sprog, der accepteres af en ikke -deterministisk Turing-maskine , der fuldfører sit arbejde i tid, der ikke overstiger f(n) . Bemærk, at der ikke er nogen hukommelsesbegrænsninger, når du definerer disse klasser.
På samme måde som tidshierarkiet introduceres et hukommelseshierarki. Klassen DSPACE (f(n)) betegner en klasse af sprog, der accepteres af deterministiske Turing-maskiner , der højst bruger f(n) hukommelsesplaceringer på arbejdsbånd. NSPACE ( f(n))- klassen er defineret som en klasse af sprog, der accepteres af ikke- deterministiske Turing-maskiner , der højst bruger f(n) hukommelsesplaceringer på arbejdsbånd. Der er ingen tidsbegrænsninger, når du definerer disse klasser.
Andre lignende klasser betragtet ovenfor er defineret på samme måde. Her er de anvendte forkortelser:
| Kompleksitetsklasser af algoritmer | |
|---|---|
| Betragtes som lys | |
| Formodes at være svært | |
| Anses for vanskelig |
|