Kompleksitetsklasse

Ein kompleksitetsklasse er ein klasse eit matematisk problem kan delast inn i, avhengig av kompleksiteten til dei naudsynte berekningane for å løyse det.

Dersom den mest effektive berekninga for å løyse eit problem har polynomisk kompleksitet, vert problemet sagt å høyre til klassen P, som er klassen av problem som kan løysast i polynomiell tid. Av særskild interesse er klassen NP, som består av ein bestemt type kompliserte problem. Desse problema reknast å ikkje kunne løysast i polynomiell tid, men dette er ikkje enno bevist. Problemet vart sett fram av den kanadiske matematikaren Stephen Cook kring 1970. Cook lukkast derimot å vise at visst eitt av problema i NP kan løysast i polynomiell tid, så kalla løysast slik. Med andre ord om eitt av problema i klassen NP høyrer til klassen P, så gjeld dette for alle, og P = NP.

Kjelder

• kompleksitetsklasser. (2012-01-03) I Store norske leksikon. Henta frå http://snl.no/kompleksitetsklasser