Kompleksitetsklasser

Kompleksitetsklasser er et sentralt begrep innen teoretisk informatikk som brukes til å klassifisere beregningsproblemer basert på ressursene de krever. De mest vanlige ressursene som vurderes er tid og minne. Et problem tildeles en kompleksitetsklasse basert på hvor mye tid eller minne som trengs for å løse det som en funksjon av inputstørrelsen. Dette gir en måte å forstå hvor "vanskelige" ulike problemer er å løse effektivt.

Den mest kjente kompleksitetsklassen er P, som omfatter alle beslutningsproblemer som kan løses av en deterministisk Turing-maskin i polynomisk tid. Et annet viktig begrep er NP, som står for nondeterministisk polynomisk tid. Problemer i NP er de som kan verifiseres av en deterministisk Turing-maskin i polynomisk tid dersom en potensiell løsning er gitt. Det store spørsmålet innen teoretisk informatikk er om P=NP, altså om alle problemer hvis løsninger kan verifiseres raskt også kan løses raskt.

Andre viktige kompleksitetsklasser inkluderer EXPTIME (eksponentiell tid), PSPACE (polynomisk plass) og L (logaritmisk plass). Hver klasse representerer en distinkt grense for beregnbarhet. Studiet av kompleksitetsklasser hjelper forskere med å identifisere hvilke problemer som sannsynligvis er uløselige i praksis, selv med fremtidige forbedringer i datamaskinytelse, og hvilke som kan forventes å bli løst effektivt. Dette har stor innvirkning på design av algoritmer og forståelsen av grensene for hva som er beregnbart.