Komplexitetsklass

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2023-07)
Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Komplexitetsklass är inom komplexitetsteori en mängd beräkningsproblem som har liknande resursbaserad komplexitet. En typisk komplexitetsklass har en definition likt:

mängden av alla problem som kan lösas av en abstrakt maskin M med O(f(n)) mycket resurser R, där n är storleken på problemet.

Till exempel är problem av komplexitetsklass NP de beslutsproblem som en icke-deterministisk turingmaskin kan lösa på polynomiell tid, medan klassen PSPACE är mängden av beslutsproblem som kan lösas av en deterministisk turingmaskin på polynomiellt utrymme.

Enklare komplexitetsklasser definieras av tre faktorer:

Problemtypen. Den vanligaste typen är beslutsproblem, men komplexitetsklassen kan även definieras av funktionsproblem (till exempel optimeringsproblem).
Beräkningsmodell. Den vanligaste beräkningsmodellen är med en deterministisk turingmaskin, men de kan även definieras av icke-deterministiska turingmaskiner, booleska kretsar och kvantturingmaskiner.
Den begränsade resursen och begränsningarna. Exempel är "polynomiell tid" och "logaritmiskt utrymme".

Många komplexitetsklasser kan karaktäriseras med den matematiska logik som krävs för att uttrycka dem.