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
Andre viktige kompleksitetsklasser inkluderer EXPTIME (eksponentiell tid), PSPACE (polynomisk plass) og L (logaritmisk plass). Hver klasse