Er der en modsætning mellem definitionen af NP som en klasse af beslutningsproblemer med polynomial-tids-verifikatorer og det faktum, at problemer i klassen P også har polynomial-time-verifikatorer?
Klassen NP, der står for Non-deterministic Polynomial time, er central for beregningskompleksitetsteori og omfatter beslutningsproblemer, der har polynomiale-tidsverifikatorer. Et beslutningsproblem er et, der kræver et ja-eller-nej-svar, og en verifikator er i denne sammenhæng en algoritme, der kontrollerer rigtigheden af en given løsning.
Det er vigtigt at skelne mellem at løse et problem (beregning) og at verificere en løsning (verifikation). I NP er fokus på, om der findes en polynomial-time verifikator, der kan bekræfte rigtigheden af en løsning.
Klassen P, der repræsenterer polynomisk tid, inkluderer beslutningsproblemer, der kan løses af en deterministisk Turing-maskine inden for polynomisk tid. For hvert problem i P er der således ikke kun en polynomial-tidsalgoritme til at finde en løsning, men der er også en polynomial-tidsalgoritme til at verificere en løsning.
Den tilsyneladende modsigelse ligger i observationen af, at hvert problem i P, der i sagens natur har en polynomial-tids-løsningsalgoritme, også har en polynomial-time-verifikator. Dette modsiger dog ikke definitionen af NP. Det definerende træk ved NP er eksistensen af en polynomial-time verifikator, uanset hvor lang tid det kan tage at finde løsningen. Det betyder, at alle problemer i P også er i NP, da deres løsninger kan verificeres i polynomisk tid.
Overvej for eksempel problemet med primtalstestning. Dette problem kan indrammes på to måder: generering af primtal og verificering af, om et givet tal er primtal. The Sieve of Eratosthenes er en algoritme til at generere alle primtal op til en vis grænse og gør det effektivt, men dens tidskompleksitet er ikke polynomiel i streng forstand, der bruges i beregningskompleksitetsteori; det betegnes ofte som O(n log log n), hvilket er bedre end lineært, men ikke strengt polynomielt i henhold til definitionen af P. På den anden side er problemet med at verificere, om et givet tal er primtal (primtalstest) en anden opgave. Effektive algoritmer, såsom AKS-primalitetstesten, giver mulighed for prime-verifikation i polynomiel tid. Derfor falder primtalstestproblemet, i forbindelse med verifikation, i klassen P, såvel som NP, fordi en løsning (om et tal er primtal) kan verificeres i polynomisk tid. Dette viser, at selvom primtalsgenerering og primtalstest er relaterede, involverer de forskellige overvejelser med hensyn til beregningsmæssig kompleksitet.
Som konklusion stemmer definitionen af NP som havende polynomielle-tids-verifikatorer med karakteren af P. Sondringen er ikke i verifikationstrinnet, men i processen med at finde løsninger: P-problemer kan løses og verificeres i polynomisk tid, mens NP-problemer kan verificeres i polynomiel tid, men det er ikke altid kendt, om de kan løses i polynomium tid.
Andre seneste spørgsmål og svar vedr Kompleksitet:
- Er PSPACE-klassen ikke lig med EXPSPACE-klassen?
- Er P kompleksitetsklassen en delmængde af PSPACE-klassen?
- Kan vi bevise, at Np- og P-klassen er ens ved at finde en effektiv polynomielløsning for ethvert NP-fuldt problem på en deterministisk TM?
- Kan NP-klassen være lig med EXPTIME-klassen?
- Er der problemer i PSPACE, som der ikke er nogen kendt NP-algoritme for?
- Kan et SAT-problem være et komplet NP-problem?
- Kan et problem være i NP-kompleksitetsklassen, hvis der er en ikke-deterministisk turingmaskine, der løser det i polynomisk tid
- NP er klassen af sprog, der har polynomielle tidsverifikatorer
- Er P og NP faktisk den samme kompleksitetsklasse?
- Er enhver kontekst frit sprog i P-kompleksitetsklassen?
Se flere spørgsmål og svar i Complexity