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".

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.

Litteratur

• Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52 (2009), no. 9, pp. 78–86.

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