komplexitetsklass

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 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.