Komplexitetsklass

Från Wikipedia
Hoppa till: navigering, sök

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.