P versus NP

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

P versus NP (også kaldet P=NP?) er et uløst problem indefor tidskompleksitet og datalogi. Informelt, 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 polynomisk tid og NP står for non-polynomisk tid, som ofte er søgende algoritmer. En NP-klasse algoritme (f.eks. O(2n)) kan eksekveres på polynomisk tid med en non-deterministisk Turing-maskine.

P=NP vil implicere, at man kan gøre enhver søge algoritme meget hurtigere. Dette betyder dog ikke, at man finde denne hurtige søge-algoritme, 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ørsmålet ikke afhænger af aksiomerne, og derfor ikke muligt at bevise.

Den person som løser problemet vil blive belønnet cirka 5.5 million kroner(1 million dollar) af "The Clay Mathematics Institute".[1]

Artikelstump Stub
Denne artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.
  1. http://www.wolframalpha.com/input/?i=P%3DNP , 18-01-2015