P=NP-problemet

Eulerdiagram for kompleksitetsklassene P, NP, NP-komplett, og NP-hardt. Under antagelsene om at henholdsvis P≠NP og P=NP.

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.

Løsningsprogresjon

Problemet blei først formulert i 1971 av Stephen Cook. Per dags dato foreligger det intet bevis for problemet enda til tross for mye forskning på problemet. Man har likevel kommet et stykke på vei siden problemet først ble formulert. Den mest fruktbare forskninga har klart blant annet å vise at eksisterende bevismetoder ikke er kraftige nok for å kunne løse problemet. Det trengs med andre ord nye bevismetoder for å kunne finne et bevis for problemet.

NP-komplette problemer er svært interessante sett i sammenheng med P=NP-problemet. Klarer man å finne ei løsning for et NP-komplett problem som kjører i polynom tid, vil det som følge av definisjonen av de NP-komplette problemene da følge at P må være lik NP. Det er fordi ethvert problem i NP skal kunne reduseres til et NP-komplett problem. Ingen har sålangt klart å finne et NP-komplett problem som lar seg løse i polynom tid.

Konsekvenser om P=NP

Konsekvensene for om P=NP vil ha store praktiske konsekvenser innenfor mange felt. Mange problemer brukes nettopp fordi de er vanskelige å løse. Flere av disse er NP-komplette problemer. Om NP skulle vært lik P og beviset for det er konstruktivt, vil det kunne bety at det blir trivielt å konstruere algoritmer for et gitt problem som kjører i polynomiell tid. Et eksempel er primtallsfaktorisering, som er svært utbredt i all form for seriøse kryptografimetoder i dag. Alle disse metodene for å kryptere vil da bli ødelagte om primtallsfaktorisering kan løses i polynomiell tid.

Samtidig om NP=P ville man fått enkle løsninger på noen av de vanskeligste problemene som omhandler algoritmer, de NP-komplette problemene. Det ville fått store konsekvenser innenfor finans, spillteori, kunstig intelligens, matematikk og mange andre fagfelter. Handelsreisendeproblemet ville for eksempel fått ei effektiv løsning som er et problem som dukker naturlig opp innenfor mange fagfelt.

Populærkultur

2012-filmen Travelling Salesman handler om fire matematikere ansatt av den amerikanske regjeringen for å løse P vs NP-problemet.

I den syvende sesongen av The Simpsons i den sjette episoden med tittelen "Treehouse of Horror VI", sees ligningen P=NP kort tid etter at Homer ved et uhell snubler inn i den "tredje dimensjonen".

I den andre sesongen av Elementary i den andre episoden med tittelen "Solve for X" handler det hele om Sherlock og Watson som etterforsker drapene på matematikere som prøvde å løse P=NP-problemet.

I romanen Rubinkretsen av Martin G. Ljungqvist dreier handlingen seg om matematikere og P vs NP-problematikken.

Litteratur

• Goldreich, Oded (2010). P, Np, and Np-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. 
• Fortnow, L. (2009). «The Status of the P versus NP problem». Communications of the ACM. 52 (9): 78. doi:10.1145/1562164.1562186. 

Eksterne lenker

• «P vs. NP: The Biggest Puzzle in Computer Science», fra YouTube, lengde 0:19:43