Kompleksitetsklasser, klasser som matematiske problemer deles inn i, avhengig av kompleksiteten til de nødvendige beregningene for å løse dem. Dersom den mest effektive beregningen for å løse et problem har polynomisk kompleksitet, sies problemet å tilhøre klassen P – klassen av problemer som kan løses i polynomiell tid. Spesiell interesse knyttes til klassen NP som består av en bestemt type kompliserte problemer. Disse problemene antas å ikke være løsbare i polynomiell tid, men denne formodningen (Cooks formodning, etter den kanadiske matematikeren Stephen Cook, som fremsatte den rundt 1970) er ikke bevist. Cook lyktes derimot i å vise at hvis ett av problemene i NP kan løses i polynomiell tid, så kan alle løses slik – med andre ord, hvis ett av problemene i klassen NP tilhører klassen P, så gjelder dette for alle, og P = NP.

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål til artikkelen? Skriv her, så får du svar fra fagansvarlig eller redaktør.

Du må være logget inn for å kommentere.