NP er klassen av språk som har polynomiske tidsverifikatorer
Klassen NP, som står for "ikke-deterministisk polynomtid," er et grunnleggende konsept i beregningskompleksitetsteori, et underfelt av teoretisk informatikk. For å forstå NP må man først ta tak i forestillingen om beslutningsproblemer, som er spørsmål med et ja-eller-nei-svar. Et språk i denne sammenhengen refererer til et sett med strenger over et eller annet alfabet, der hver streng koder for en forekomst av et beslutningsproblem.
Et språk (L) sies å være i NP hvis det finnes en polynom-tidsbekreftelse for (L). En verifikator er en deterministisk algoritme (V) som tar to innganger: en forekomst (x) og et sertifikat (y). Attesten (y) er også kjent som et "vitne" eller "bevis". Verifikatoren (V) sjekker om sertifikatet (y) bekrefter at (x) tilhører språket (L). Formelt er et språk (L) i NP hvis det finnes en polynomisk-tidsalgoritme (V) og et polynom (p(n)), slik at for hver streng (x i L), eksisterer det en streng (y) med ( |y|. lek p(|x|)) og (V(x, y) = 1). Omvendt, for hver streng (x notin L), er det ingen streng (y) slik at (V(x, y) = 1).
For å belyse dette konseptet, vurder det velkjente problemet med "Boolean satisfiability" (SAT). SAT-problemet spør om det eksisterer en tilordning av sannhetsverdier til variabler i en gitt boolsk formel slik at formelen evalueres til sann. SAT-problemet er i NP fordi gitt en boolsk formel ( phi ) og en tilordning ( alfa ) av sannhetsverdier til dens variabler, kan man verifisere i polynomtid om ( alfa ) tilfredsstiller ( phi ). Her er instansen ( x ) den boolske formelen ( phi ), og sertifikatet ( y ) er oppgaven ( alfa ). Verifikatoren ( V ) sjekker om ( alfa ) gjør ( phi ) sann, noe som kan gjøres i polynomisk tid med hensyn til størrelsen på ( phi ).
Et annet illustrerende eksempel er "Hamiltonian Path"-problemet. Dette problemet spør om det finnes en bane i en gitt graf som besøker hvert toppunkt nøyaktig én gang. Hamiltonian Path-problemet er også i NP fordi, gitt en graf ( G ) og en sekvens av toppunkter ( P ), kan man verifisere i polynomisk tid om ( P ) er en Hamiltonsk bane i ( G ). I dette tilfellet er instansen ( x ) grafen ( G ), og sertifikatet ( y ) er sekvensen av hjørner ( P ). Verifikatoren ( V ) sjekker om ( P ) danner en Hamiltonsk bane, noe som kan gjøres i polynomisk tid med hensyn til størrelsen på ( G ).
Konseptet med polynom-tidsverifiserbarhet er viktig fordi det gir en måte å karakterisere problemer som er effektivt kontrollerbare, selv om det å finne løsningen kan være beregningsmessig umulig. Dette fører til det berømte spørsmålet om ( P = NP ), som spør om ethvert problem hvis løsning kan verifiseres i polynomtid også kan løses i polynomtid. Klassen ( P ) består av beslutningsproblemer som kan løses i polynomisk tid av en deterministisk Turing-maskin. Hvis ( P = NP ), vil det bety at hvert problem med en polynom-tidsverifikator også har en polynom-tidsløser. Dette spørsmålet er fortsatt et av de viktigste åpne problemene innen informatikk.
En av nøkkelegenskapene til NP er at den er lukket under polynom-tidsreduksjoner. En polynom-tidsreduksjon fra et språk ( L_1 ) til et språk ( L_2 ) er en polynom-tidsberegnbar funksjon ( f ) slik at ( x i L_1 ) hvis og bare hvis ( f(x) i L_2 ). Hvis det eksisterer en polynom-tidsreduksjon fra (L_1) til (L_2) og (L_2) er i NP, så er (L_1) også i NP. Denne egenskapen er medvirkende til studiet av NP-fullstendighet, som identifiserer de "vanskeligste" problemene i NP. Et problem er NP-fullstendig hvis det er i NP og hvert problem i NP kan reduseres til det i polynomisk tid. SAT-problemet var det første problemet som ble bevist å være NP-komplett, og det tjener som grunnlag for å bevise NP-fullstendigheten til andre problemer.
For ytterligere å illustrere konseptet med polynom-tidsverifiserbarhet, vurder "Subset Sum"-problemet. Dette problemet spør om det finnes en delmengde av et gitt sett med heltall som summerer til en spesifisert målverdi. Subset Sum-problemet er i NP fordi gitt et sett med heltall ( S ), en målverdi ( t ) og en delmengde ( S' ) av ( S ), kan man verifisere i polynomtid om summen av elementene i (S') er lik (t). Her er instansen ( x ) paret ( (S, t) ), og sertifikatet ( y ) er delmengden ( S' ). Verifikatoren ( V ) sjekker om summen av elementene i ( S' ) er lik ( t ), noe som kan gjøres i polynomisk tid med hensyn til størrelsen på ( S ).
Betydningen av polynomisk-tidsverifiserbarhet strekker seg utover teoretiske betraktninger. Rent praktisk betyr det at for problemer i NP, hvis et forslag til løsning (sertifikat) er gitt, kan det kontrolleres effektivt. Dette har betydelige implikasjoner for kryptografiske protokoller, optimaliseringsproblemer og ulike felt der det er viktig å verifisere riktigheten av en løsning.
For å oppsummere, omfatter klassen NP beslutningsproblemer som en foreslått løsning kan verifiseres for i polynomisk tid ved hjelp av en deterministisk algoritme. Dette konseptet er grunnleggende i beregningsmessig kompleksitetsteori og har dype implikasjoner for både teoretiske og praktiske aspekter ved informatikk. Studiet av NP, polynom-tidsverifiserbarhet og relaterte konsepter som NP-fullstendighet fortsetter å være et levende og kritisk forskningsområde.
Andre nyere spørsmål og svar vedr kompleksitet:
- Er ikke PSPACE-klassen lik EXPSPACE-klassen?
- Er P kompleksitetsklassen en undergruppe av PSPACE-klassen?
- Kan vi bevise at Np- og P-klassen er like ved å finne en effektiv polynomløsning for ethvert NP-komplett problem på en deterministisk TM?
- Kan NP-klassen være lik EXPTIME-klassen?
- Er det problemer i PSPACE som det ikke er noen kjent NP-algoritme for?
- Kan et SAT-problem være et NP-komplett problem?
- Kan et problem være i NP-kompleksitetsklassen hvis det er en ikke-deterministisk turingmaskin som vil løse det i polynomisk tid
- Er P og NP faktisk samme kompleksitetsklasse?
- Er enhver kontekst fritt språk i P-kompleksitetsklassen?
- Er det en motsetning mellom definisjonen av NP som en klasse av beslutningsproblemer med polynom-tids-verifikatorer og det faktum at problemer i klassen P også har polynom-tids-verifikatorer?
Se flere spørsmål og svar i Complexity