P=NP-problemet
From Wikipedia, the free encyclopedia
P=NP-problemet er et uløst problem innen matematikken og informatikken. Det er kjent som et av de sju millenniumsproblemene innen matematikken med en utlovet premie på 1 million dollar for ei løsning på problemet. Det går ut på om de to kompleksitetsklassene P og NP er like eller ikke. Det er flere måter å se problemstillinga på. Uformelt kan man si at problemet går ut på at hvis det for ethvert problem hvor det går an å effektivt sjekke om ei gitt løsning er korrekt, om det da finnes en effektiv måte for å finne ei løsning også. Mer presist, med ordet «effektivt» menes det deterministisk polynomiell tid.
En annen måte å se problemstillinga på er om det for ethvert problem i NP finnes en algoritme som kan løse problemet i deterministisk polynomiell tid, altså at den kjører i polynomiell tid på ei deterministisk turingmaskin. Da vil NP per definisjon være lik P. NP er definert som kompleksitetsklassa for problemene som kan løses i ikke-deterministisk polynomiell tid.
Mye av den teorien som i dag eksisterer på kompleksitetsteori bygger på at NP og P ikke er like. Det foreligger derfor brede konsensus om at de er forskjellige kompleksitetsklasser. Samtidig har man intet bevis for det og det foreligger også argumenter for at de er like.