Visa källa för 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,<blockquote>Finns det något beslutsproblem som kan lösas av en icke-deterministisk [[turingmaskin]] i polynomiell tid, dvs det ligger i komplexitetsklassen '''NP''', men inte av en deterministisk turingmaskin, dvs det ligger inte i komplexitetsklassen '''P'''?</blockquote>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 <ref>[http://www.claymath.org/millennium/ Clay Mathematics Institute] {{Wayback|url=http://www.claymath.org/millennium/ |date=20080108223641 }}</ref> valde problemet som ett av [[millennieproblemen]], så den som löser problemet vinner 1&nbsp;000&nbsp;000 dollar.<ref name="CMI Millennium Prize Problems">{{Webbref|titel=Millennium Prize problems |url=http://www.claymath.org/millennium/ |datum=2000-05-24 |hämtdatum=11 maj 2010 |arkivurl=https://web.archive.org/web/20080108223641/http://www.claymath.org/millennium/ |arkivdatum=8 januari 2008 }}</ref>

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 då ett sätt att hitta en lösning snabbt också?

== Beskrivning ==
Betrakta ett [[ekvationssystem]] med flera obekanta:
:<math>
\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}
</math>
Att lösa detta system är enkelt. [[Gausselimination]] har varit känt länge och kräver i storleksordningen <math>n^3</math> additioner och multiplikationer. Mycket stora ekvationssystem kan lösas effektivt på datorer. Problemet att lösa ett ekvationssystem sägs ta polynomiell tid eftersom <math>n^3</math> är ett [[polynom]].

Om vi lägger till kravet att
:<math>x_{i} \ge 0 \,</math> för alla  <math>i</math>
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 <math>n^4</math> operationer. Det går dock att lösa mycket stora linjärprogram på moderna datorer (<math>n > 1000000</math>). 

Om vi istället skulle kräva att
:<math>x_{i} \,</math> är ett '''heltal''' för alla  <math>i</math>
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 [[Advanced Encryption Standard|AES]]-[[kryptering]]<ref name=lipton>[http://rjlipton.wordpress.com/2010/06/26/stating-pnp-without-turing-machines/ Stating P=NP Without Turing Machines]</ref>
* [[Faktorisering|Faktorisera]] heltal.<ref name=lipton />
* ...
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]].
 
<math>P = \{L:L=L(M) \mbox{ för någon deterministisk polynomiell-tid turingmaskin } M\}</math>

där <math>L(M)=\{w\in\Sigma^* : \text{ accepterar } w\}</math> och <math>\Sigma^*</math> ä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 <math>k \in N</math> så att <math>T_{M}(n)\in\; </math>''O''<math>(n^{k})</math>,
::där <math>T_{M}(n) = \max\{ t_{M}(w) : w\in\Sigma^{*}, \left|w\right| = n \}</math>
::och <math>t_{M}(w) = \text{ antalet steg det tar för M att stanna på indatan } w.</math>

'''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 <math>L</math> vara ett språk över ett ändligt alfabet <math>\Sigma</math>

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

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

En turingmaskin som kontrollerar <math>L_{R}</math> kallas en verifierare för <math>L</math> och <math>y</math> så att <math>(x,y)\in R</math> kallas ett certifikat för <math>x </math> i <math>L</math>.<ref name="Official Problem Description">{{Tidningsref|författare=Cook |förnamn=Stephen |författarlänk=Stephen Cook |titel=The P versus NP Problem |utgivare=[[Clay Mathematics Institute]] |datum=2000 |month=April |url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf |hämtdatum=11 maj 2010 |arkivurl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf |arkivdatum=12 december 2010 }}</ref>

== 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 <math>L_{i}</math> är ett språk över ett ändligt alfabet <math>\Sigma_{i}, i=1,2</math>, så sägs <math>L_{1}</math> vara reducerbar i polynomiell tid till <math>L_{2}</math> om och endast om:
# Det finns <math>f: \Sigma^*_{1} \rightarrow \Sigma^*_{2}</math> så att, <math>x \in L_{1} \Leftrightarrow f(x) \in L_{2}</math> för alla <math>x \in \Sigma^*_{1}</math>
# <math>f(x)</math> kan beräknas i polynomiell tid på en deterministisk turingmaskin.

<math>L</math> sägs vara '''NP'''-fullständigt om och endast om:
# <math>L \in NP</math>
# För alla <math>L' \in NP</math> är <math>L'</math> reducerbar i polynomiell tid till <math>L</math><ref name="Official Problem Description"/>

== 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 [[komplexitetsteori|komplexitetsläran]] inte går att använda.<ref name="cs.uchicago.edu">[[Lance Fortnow]], [http://delivery.acm.org/10.1145/1570000/1562186/p78-fortnow.pdf?ip=2.67.113.88&id=1562186&acc=OPEN&key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E6D218144511F3437&__acm__=1539559041_8f8e7397f781390728ea98978ab56545 ''The status of the P versus NP problem''], Communications of the ACM 52 (2009), no.&nbsp;9, pp.&nbsp;78–86. {{doi|10.1145/1562164.1562186}}</ref>

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

{{citat|If P&nbsp;<nowiki>=</nowiki>&nbsp;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]]}}

{{citat|...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 [[Clay Math Institute#Millennium Prize Problems|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.<ref name="cs.uchicago.edu"/> 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. 

== Referenser ==
=== Noter ===
<references/> 

== Externa länkar ==
* [http://www.claymath.org/millennium/ Clay Mathematics Institute]
* [https://web.archive.org/web/20081204124245/http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#p ''Complexity Zoo'' Class P]
* [https://web.archive.org/web/20100727020050/http://qwiki.stanford.edu/wiki/Complexity_Zoo:N#np ''Complexity Zoo'' Class NP]

<!-- inga specialtecken i sorteringen -->

{{STANDARDSORTERING:P np}}
[[Kategori:Datavetenskap]]
[[Kategori:Olösta matematiska problem]]