P versus NP

P versus NP (også kaldet P=NP?) er et uløst problem indenfor tidskompleksitet og datalogi. Uformelt, kan problemet beskrives som:

"Kan alle algoritmer, hvis svar kan verificeres af en computer hurtigt, også løses af en computer hurtigt?"

Mere formelt kan det skrives som:

"Kan alle algoritmer, hvis resultat kan verificeres på polynomisk tid, også komputeres på polynomisk tid?"

Problemet spørger om alle elementer i P-klassen, også kan findes i NP-klassen. P står for polynomiel tid og NP står for non-deterministisk polynomiel tid, som ofte er søgende algoritmer. En NP-klasse algoritme (f.eks. O(n²)) kan eksekveres på polynomiel tid med en non-deterministisk Turing-maskine.

P=NP vil implicere, at man kan gøre enhver søgealgoritme meget hurtigere. Dette betyder dog ikke, at man finder denne hurtige søgealgoritme, bare ved at bevise P=NP.

Problemet er en del af Millenniumproblemerne.

I en undersøgelse, hvor man spurgte 100 videnskabsfolk, troede 61, at svaret var nej, 9 troede, at svaret var ja, 22 var usikre og 8 troede, at spørgsmålet ikke afhænger af aksiomerne, og derfor ikke er muligt at bevise.

Den person, som løser problemet, vil blive belønnet med 1 million US Dollar (cirka 6,77 millioner DKK) af "The Clay Mathematics Institute".^[1]

Populær kultur

Filmen Traveling Salesman fra 2012 er historien om fire matematikere, der er hyret af den amerikanske regering til at løse P vs NP-problemet.

I den syvende sæson af The Simpsons i det sjette afsnit med titlen "Treehouse of Horror VI", ses ligningen P=NP kort efter, at Homer ved et uheld faldt ind i den "tredje dimension".

I anden sæson af Elementary i det andet afsnit med titlen "Solve for X", handler plottet om, at Sherlock og Watson efterforsker mordene på matematikere, der forsøgte at løse P vs NP.

I romanen Rubinkretsen af Martin G. Ljungqvist kredser plottet om matematikere og P vs NP-problemet.

Noter

1. http://www.wolframalpha.com/input/?i=P%3DNP , 18-01-2015

Litteratur

• 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

Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.