complexiteitsklassen

Complexiteitsklassen zijn verzamelingen van beslissingsproblemen die dezelfde asymptotische afhankelijkheid van hulpmiddelen zoals tijd of ruimte hebben. Ze geven aan hoe moeilijk een probleem op te lossen is, gemeten naar de benodigde bronnen op een (deterministische of niet-deterministische) Turingmachine. Vaak gaat het om tijds- of ruimtebeperkingen, en om het verschil tussen deterministische en niet-deterministische berekeningen.

De bekendste klassen zijn P en NP. P bevat beslissingsproblemen die in polynomiale tijd opgelost kunnen worden door een deterministische Turingmachine. NP omvat problemen waarvoor een ja-antwoord in polynomiale tijd geverifieerd kan worden op een niet-deterministische machine (of, equivalenter, waarbij een bewijs in polynomiale tijd kan worden geverifieerd).

Daarnaast zijn er co-NP (de complementen van NP-problemen) en PSPACE (problemen die met polynomiale ruimte op te lossen zijn). PSPACE bevat P en NP en staat bekend als een krachtige ruimteklasse. EXP of EXPTIME omvat beslissingsproblemen die in exponentiële tijd opgelost kunnen worden. Andere belangrijke klassen zijn L en NL (respectievelijk logaritmische ruimte deterministisch en niet-deterministisch).

Compleetheidsbegrippen, gebaseerd op reducties, tonen de moeilijkste problemen binnen een klasse aan. Een probleem is NP-compleet als het in NP ligt en elke NP-probleem in polynomiale tijd kan worden gereduceerd naar dit probleem. SAT is het klassieke NP-complete probleem; andere voorbeelden zijn 3-SAT, CLIQUE en Hamiltoniaanse cycle. PSPACE-complete en EXP-complete problemen bestaan ook, zoals QBF voor PSPACE-complete en bepaalde spel- of logiekproblemen voor EXP-complete.

Relaties tussen klassen zijn onder meer P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, en PH ⊆ PSPACE. De vraag of P gelijk is aan NP (P vs NP) is nog onopgelost.