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
Daarnaast zijn er co-NP (de complementen van NP-problemen) en PSPACE (problemen die met polynomiale ruimte op
Compleetheidsbegrippen, gebaseerd op reducties, tonen de moeilijkste problemen binnen een klasse aan. Een probleem is NP-compleet
Relaties tussen klassen zijn onder meer P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, en PH ⊆ PSPACE. De vraag of