P=NP?

P=NP? är ett problem inom datavetenskap. Problemet handlar om huruvida två klasser av beslutsproblem, P och NP, är samma klass eller ej. Problemet är inte löst och anses av vissa som det viktigaste inom datavetenskapen.

Problemet lyder,

Finns det något beslutsproblem, vars lösning kan verifieras på polynomiell tid, dvs det ligger i komplexitetsklassen NP, men som inte kan lösas på polynomiell tid, dvs det ligger inte i komplexitetsklassen P?

Problemet är viktigt inom datavetenskapen, eftersom många svåra problem finns i klassen NP. Problemet ger viktig information om hur mycket tid man kan förvänta sig att dessa problem borde ta. Clay Mathematics Institute ^[1] valde problemet som ett av millennieproblemen, så den som löser problemet vinner 1 000 000 dollar.^[2]

Ett förenklat sätt att förklara problemet är: om du har ett problem där det går fort att kontrollera att en lösning är korrekt, finns det alltid då ett sätt att hitta en lösning snabbt också?

Beskrivning

Betrakta ett ekvationssystem med flera obekanta:

{\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\ldots +a_{2n}x_{n}=b_{2}\\\vdots \\a_{n1}x_{1}+a_{n2}x_{2}+\ldots +a_{nn}x_{n}=b_{n}\\\end{cases}}

Att lösa detta system är enkelt. Gausselimination har varit känt länge och kräver i storleksordningen n³ additioner och multiplikationer. Mycket stora ekvationssystem kan lösas effektivt på datorer. Problemet att lösa ett ekvationssystem sägs ta polynomiell tid eftersom n³ är ett polynom.

Om vi lägger till kravet att x_i ≥ 0 för alla i blir problemet svårare. Problemet kallas då linjärprogrammering och är en stor klass av problem som kan användas till att lösa transport- och planeringsproblem, till flödesberäkningar och inom ekonomi. Det finns dock effektiva algoritmer även för att lösa linjärprogram. Metoderna är inte lika effektiva som för vanliga ekvationssystem och kräver i storlekordningen n⁴ operationer. Det går dock att lösa mycket stora linjärprogram på moderna datorer (n > 1 000 000).

Om vi istället skulle kräva att x_i ∈ ℤ för alla i kallas problemet heltalsprogrammering vilket är en mycket stor klass av problem. Många problem inom kombinatorik och talteori kan formuleras som heltalsprogram. Till exempel innefattar denna klass av problem:

Att knäcka AES-kryptering^[3]
Faktorisera heltal.^[3]
...

Att effektivt kunna lösa ekvationssystem över heltal skulle få enorma följder. Frågan "P=NP?" kan formuleras som:

"Går det effektivt att lösa ekvationssystem över heltal?"

Bakgrund

Frågan om P är detsamma som NP togs upp 1971 av Stephen Cook i artikeln The Complexity of Theorem Proving Procedures, som presenterades på 1971 ACM SIGACT Symposium on the Theory of Computing. I artikeln bevisar han också existensen av ett NP-fullständigt problem. Frågan om P=NP diskuterades på konferensen och när man inte kom fram till någon slutsats bestämde man sig för att lösa problemet senare. Dock så har ingen lösning hittats än så länge, trots att detta är ett av områdena inom datavetenskapen som mycket forskning lagts på.

P och NP

P och NP är benämningar på komplexitetsklasser. P är mängden beslutsproblem som går att lösa i polynomiell tid på en turingmaskin. Tiden det tar att lösa dessa problem på en dator växer alltså polynomiellt mot storleken på indatan. Som regel går dessa problem att lösa på ett effektivt sätt.

NP är mängden beslutsproblem som går att lösa i polynomiell tid på en ickedeterministisk turingmaskin. Tiden det tar att lösa dessa problem växer alltså också polynomiellt mot storleken på indata, men här krävs en ickedeterministisk turingmaskin. Detta är en turingmaskin som kan utföra flera operationer samtidigt, till skillnad från en vanlig turingmaskin, som bara kan utföra en operation i varje tillstånd. En ickedeterministisk turingmaskin kan alltså ta flera "vägar" i uträkningen samtidigt. Det går också att se det som att den ickedeterministiska turingmaskinen vet vilken väg som kommer att leda rätt och alltid väljer denna bästa väg. Alla problem i P ligger också i NP eftersom en turingmaskin är ett specialfall av en ickedeteriministisk turingmaskin.

NP kan också definieras som mängden av de problem som kan verifieras i polynomiell tid på en turingmaskin. Det betyder att om man har en lösning till ett NP-problem så går det att kontrollera att den är korrekt på en vanlig turingmaskin på polynomiell tid. Det behöver inte finnas något snabbt sätt att verifiera att en lösning inte existerar.

Definition

Ett beslutsproblem är ett problem som har en sträng som indata och som utdata ja eller nej.

P definieras som mängden språk som kan beslutas på en polynomiell-tid turingmaskin.

$P=\{L:L=L(M){\mbox{ för någon deterministisk polynomiell-tid turingmaskin }}M\}$

där $L(M)=\{w\in \Sigma ^{*}:{\text{ accepterar }}w\}$ och $\Sigma ^{*}$ är mängden av alla indata.

Där en polynomiell-tid turingmaskin är en deterministisk turingmaskin M där följande är sant

M stannar för alla indata-strängar w
det finns $k\in N$ så att $T_{M}(n)\in \;$ O $(n^{k})$ ,

där

T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},\left|w\right|=n\}

och

t_{M}(w)={\text{ antalet steg det tar för M att stanna på indatan }}w.

NP kan definieras på samma sätt som P men med en ickedeterministisk turingmaskin. Oftast använder man dock en definition med certifikat och verifierare. Ett certifikat kan ses som en lösning till problemet och verifieraren som en turingmaskin som verifierar att certifikatet är korrekt. Då definieras NP som mängden språk som över ett ändligt alfabet som har en verifierare som körs på polynomiell tid på en turingmaskin. En verifierare definieras genom:

Låt $L$ vara ett språk över ett ändligt alfabet $\Sigma$

$L\in \mathbf {NP}$ om och endast om det finns en binär relation $R\subset \Sigma ^{*}\times \Sigma ^{*}$ och ett positivt heltal $k$ så att följande villkor är sanna:

För alla $x\in \Sigma ^{*},x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ så att $(x,y)\in R\$ och $\left|y\right|\in O(\left|x\right|^{k})$
Språket $L_{R}=\{x\#y:(x,y)\in R\}$ över $\Sigma \cup \{\#\}$ ger ett svar ja eller nej på en polynomiell-tid turingmaskin.

En turingmaskin som kontrollerar $L_{R}$ kallas en verifierare för $L$ och $y$ så att $(x,y)\in R$ kallas ett certifikat för $x$ i $L$ .^[4]

NP-fullständighet

För att angripa P=NP problemet utnyttjar man klassen NP-fullständig eller NPC som är en förkortning för NP-Complete. NPC är en underklass till NP. Ett NP-fullständigt problem p har den egenskapen att alla andra NP-problem kan transformeras till p i polynomiell tid. Detta betyder att om ett NP-fullständigt problem kan lösas på polynomiell tid, så kan också alla andra problem i NP det. Omvänt så gäller att om det bevisas att ett NP-problem inte ligger i P så gör inte heller något NP-fullständigt problem det. För att visa att P=NP räcker det alltså att lösa ett NP-fullständigt problem

En stor mängd beräkningsproblem har visats vara NP-fullständiga. Ett exempel är att avgöra om det finns en summa av någon delmängd av en mängd heltal som är lika med noll. Andra kända NPC-problem är beslutsvarianterna av Kappsäcksproblemet och Handelsresandeproblemet. Det finns mer än 3000 problem som är NP-fullständiga. Många av dessa problem uppkommer i naturliga sammanhang, till exempel i algoritmer för routning av nätverkstrafik och datalagring. Dessutom är flera vanliga pussel och spel NP-fullständiga, bland andra Sänka Skepp, Tetris och Mastermind.

Svårighet

NP-fullständiga problem är de svåraste problemen i NP. Trots det så går det ofta att hitta approximativa algoritmer som löser många NP-fullständiga problem tillräckligt bra för att kunna användas i praktiska tillämpningar. I praktiken finns ofta algoritmer som löser problemen optimalt inom rimliga tider, trots att det i värsta fall kan ta mycket lång tid. Dessa värsta fall uppkommer dock så sällan att de inte innebär några problem. Det finns också problem som ligger i P som i praktiken är mycket svåra att lösa. Att avgöra om ett tal är ett primtal är till exempel ett problem i P som i praktiken är svårt när talen blir tillräckligt stora. Trots detta brukar man säga att P-problem är lätta och NP-fullständiga problem är svåra. Att NP-fullständiga problem också kan vara mycket svåra används till exempel inom kryptologi, då många krypteringar bygger på något NP-fullständigt problem.

Definition

Om $L_{i}$ är ett språk över ett ändligt alfabet $\Sigma _{i},i=1,2$ , så sägs $L_{1}$ vara reducerbar i polynomiell tid till $L_{2}$ om och endast om:

Det finns $f:\Sigma _{1}^{*}\rightarrow \Sigma _{2}^{*}$ så att, $x\in L_{1}\Leftrightarrow f(x)\in L_{2}$ för alla $x\in \Sigma _{1}^{*}$
$f(x)$ kan beräknas i polynomiell tid på en deterministisk turingmaskin.

$L$ sägs vara NP-fullständigt om och endast om:

$L\in NP$
För alla $L'\in NP$ är $L'$ reducerbar i polynomiell tid till $L$ ^[4]

Bevis

Än så länge finns inga bevis varken för eller emot att P är detsamma som NP. Det kan till och med vara så att problemet är oberoende av de axiomsystem som används och därför varken går att bevisa eller motbevisa. Något som har visats är att en del metoder som vanligtvis används för att bevisa satser inom komplexitetsläran inte går att använda.^[5]

Om det skulle bevisas att P=NP så skulle det innebära en stor förändring inom många områden.

”	If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...	„
– Scott Aaronson, MIT

”	...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.	„
– Stephen Cook

Skulle det vara så att NP är detsamma som P skulle det kunna innebära att det är lika svårt att lösa problem som att kontrollera att en lösning är korrekt. Till exempel skulle asymmetrisk kryptering vara omöjlig. Det skulle också betyda att alla NP problem skulle vara lätta att lösa. Det skulle gå att göra optimala algoritmer för logistik och transporter, som skulle bli billigare och effektivare. Man skulle kunna hitta korta varianter av matematiska bevis. Språkförståelse och översättning skulle också bli enkelt.^[5] Det är dock möjligt att P=NP utan att det går att praktiskt hitta lösningar till NP-fullständiga problem. Beviset skulle kunna vara icke-konstruktivt och inte ge någon algoritm för att lösa problem eller också skulle beräkningarna inte vara praktiskt genomförbara.

Populärkultur

Filmen Travelling Salesman från 2012 är en berättelse om fyra matematiker som anlitats av den amerikanska regeringen för att lösa P vs NP-problemet.

I den sjunde säsongen av The Simpsons i sjätte avsnittet med titeln "Treehouse of Horror VI" ses ekvationen P=NP kort efter att Homer av misstag snubblat in i den "tredje dimensionen".

I den andra säsongen av Elementary i andra avsnittet med titeln "Solve for X" kretsar handlingen kring Sherlock och Watson som undersöker morden på matematiker som försökte lösa P vs NP.

I romanen Rubinkretsen av Martin G. Ljungqvist kretsar handlingen kring matematiker och P vs NP-problemet.

Referenser

Noter

^ Clay Mathematics Institute Arkiverad 8 januari 2008 hämtat från the Wayback Machine.
^ ”Millennium Prize problems”. 24 maj 2000. Arkiverad från originalet den 8 januari 2008. https://web.archive.org/web/20080108223641/http://www.claymath.org/millennium/. Läst 11 maj 2010.
^ [a b] Stating P=NP Without Turing Machines
^ [a b] Cook, Stephen (14 oktober 2000). ”The P versus NP Problem”. Clay Mathematics Institute. Arkiverad från originalet den 12 december 2010. https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf. Läst 11 maj 2010.
^ [a b] Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52 (2009), no. 9, pp. 78–86. doi:10.1145/1562164.1562186

Externa länkar

[1] Clay Mathematics Institute Arkiverad 8 januari 2008 hämtat från the Wayback Machine.

[CMI_Millennium_Prize_Problems-2] ”Millennium Prize problems”. 24 maj 2000. Arkiverad från originalet den 8 januari 2008. https://web.archive.org/web/20080108223641/http://www.claymath.org/millennium/. Läst 11 maj 2010.

[lipton-3] [a b] Stating P=NP Without Turing Machines

[Official_Problem_Description-4] [a b] Cook, Stephen (14 oktober 2000). ”The P versus NP Problem”. Clay Mathematics Institute. Arkiverad från originalet den 12 december 2010. https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf. Läst 11 maj 2010.

[cs.uchicago.edu-5] [a b] Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52 (2009), no. 9, pp. 78–86. doi:10.1145/1562164.1562186

[1]

[2]

[3]

[4]

[5]