NP er klassen af sprog, der har polynomielle tidsverifikatorer
Klassen NP, som står for "ikke-deterministisk polynomisk tid," er et grundlæggende begreb i beregningsmæssig kompleksitetsteori, et underområde af teoretisk datalogi. For at forstå NP skal man først forstå begrebet beslutningsproblemer, som er spørgsmål med et ja-eller-nej-svar. Et sprog refererer i denne sammenhæng til et sæt strenge over et eller andet alfabet, hvor hver streng koder for en instans af et beslutningsproblem.
Et sprog (L) siges at være i NP, hvis der findes en polynomiel-tidsbekræftelse for (L). En verifikator er en deterministisk algoritme (V), der tager to input: en instans (x) og et certifikat (y). Attesten (y) er også kendt som et "vidne" eller "bevis". Verifikatoren (V) kontrollerer, om certifikatet (y) bekræfter, at (x) hører til sproget (L). Formelt er et sprog (L) i NP, hvis der findes en polynomial-tidsalgoritme (V) og et polynomium (p(n)), således at der for hver streng (x i L) eksisterer en streng (y) med ( |y|. leq p(|x|)) og (V(x, y) = 1). Omvendt, for hver streng (x notin L), er der ingen streng (y), sådan at (V(x, y) = 1).
For at belyse dette koncept, overvej det velkendte problem med "Boolean satisfiability" (SAT). SAT-problemet spørger, om der findes en tildeling af sandhedsværdier til variabler i en given boolsk formel, således at formlen evalueres til sand. SAT-problemet er i NP, fordi givet en boolsk formel ( phi ) og en tildeling ( alfa ) af sandhedsværdier til dens variabler, kan man verificere i polynomisk tid, om (alfa) opfylder (phi). Her er instansen ( x ) den boolske formel ( phi ), og certifikatet ( y ) er opgaven ( alfa ). Verifikatoren (V) kontrollerer, om (alfa) gør (phi) sand, hvilket kan gøres i polynomisk tid med hensyn til størrelsen af (phi).
Et andet illustrativt eksempel er "Hamiltonian Path"-problemet. Dette problem spørger, om der findes en sti i en given graf, der besøger hvert hjørne nøjagtigt én gang. Hamiltonian Path-problemet er også i NP, fordi givet en graf ( G ) og en sekvens af toppunkter ( P ), kan man verificere i polynomisk tid, om ( P ) er en Hamiltonsk sti i ( G ). I dette tilfælde er instansen ( x ) grafen ( G ), og certifikatet ( y ) er sekvensen af hjørner ( P ). Verifikatoren (V) kontrollerer, om (P) danner en Hamiltonsk sti, hvilket kan udføres i polynomiel tid med hensyn til størrelsen af (G).
Konceptet med polynomium-tids-verificerbarhed er vigtigt, fordi det giver en måde at karakterisere problemer, der er effektivt kontrollerbare, selvom det kan være beregningsmæssigt umuligt at finde løsningen. Dette fører til det berømte spørgsmål om (P = NP), som spørger, om ethvert problem, hvis løsning kan verificeres i polynomiel tid, også kan løses i polynomiel tid. Klassen ( P ) består af beslutningsproblemer, der kan løses i polynomiel tid af en deterministisk Turing-maskine. Hvis ( P = NP ), ville det betyde, at hvert problem med en polynomial-time verifikator også har en polynomial-time solver. Dette spørgsmål er fortsat et af de vigtigste åbne problemer inden for datalogi.
En af nøgleegenskaberne ved NP er, at den er lukket under polynomiske tidsreduktioner. En polynomieltidsreduktion fra et sprog (L_1) til et sprog (L_2) er en polynomisk-tidsberegnbar funktion (f), sådan at (x i L_1) hvis og kun hvis (f(x) i L_2). Hvis der eksisterer en polynomisk tidsreduktion fra (L_1) til (L_2) og (L_2) er i NP, så er (L_1) også i NP. Denne egenskab er medvirkende til studiet af NP-fuldstændighed, som identificerer de "sværeste" problemer i NP. Et problem er NP-komplet, hvis det er i NP, og ethvert problem i NP kan reduceres til det i polynomisk tid. SAT-problemet var det første problem, der viste sig at være NP-komplet, og det tjener som grundlag for at bevise NP-fuldstændigheden af andre problemer.
For yderligere at illustrere konceptet med polynomisk-tids-verificerbarhed, overveje "Subset Sum"-problemet. Dette problem spørger, om der eksisterer en delmængde af et givet sæt af heltal, der summerer til en specificeret målværdi. Delmængdesum-problemet er i NP, fordi givet et sæt af heltal (S), en målværdi (t) og en delmængde (S') af (S), kan man verificere i polynomisk tid, om summen af elementerne i (S') er lig med (t). Her er instansen (x) parret ((S,t)), og certifikatet (y) er delmængden (S'). Verifikatoren (V) kontrollerer, om summen af elementerne i (S') er lig med (t), hvilket kan gøres i polynomisk tid med hensyn til størrelsen af (S).
Betydningen af polynomium-tids-verificerbarhed rækker ud over teoretiske overvejelser. Rent praktisk betyder det, at for problemer i NP, hvis en foreslået løsning (certifikat) leveres, kan den kontrolleres effektivt. Dette har betydelige konsekvenser for kryptografiske protokoller, optimeringsproblemer og forskellige områder, hvor det er vigtigt at verificere rigtigheden af en løsning.
For at opsummere, omfatter klassen NP beslutningsproblemer, for hvilke en foreslået løsning kan verificeres i polynomiel tid ved hjælp af en deterministisk algoritme. Dette koncept er grundlæggende i beregningsmæssig kompleksitetsteori og har dybtgående implikationer for både teoretiske og praktiske aspekter af datalogi. Studiet af NP, polynomial-tids-verificerbarhed og relaterede begreber såsom NP-fuldstændighed er fortsat et levende og kritisk forskningsområde.
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
- Er P og NP faktisk den samme kompleksitetsklasse?
- Er enhver kontekst frit sprog i P-kompleksitetsklassen?
- 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?
Se flere spørgsmål og svar i Complexity