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.