P=NP-problemet

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk
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 stort 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[rediger | rediger kilde]

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[rediger | rediger kilde]

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.

Litteratur[rediger | rediger kilde]