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

Noter

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