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.

Artikelstump Stub
Denne artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.