Klassen NP, som står för "icke-deterministisk polynomtid", är ett grundläggande begrepp inom beräkningskomplexitetsteori, ett underområde inom teoretisk datavetenskap. För att förstå NP måste man först förstå begreppet beslutsproblem, som är frågor med ett ja-eller-nej-svar. Ett språk i detta sammanhang hänvisar till en uppsättning strängar över något alfabet, där varje sträng kodar en instans av ett beslutsproblem.
Ett språk (L) sägs vara i NP om det finns en polynom-tidsverifierare för (L). En verifierare är en deterministisk algoritm (V) som tar två ingångar: en instans (x) och ett certifikat (y). Intyget (y) är också känt som ett "vittne" eller "bevis". Verifieraren (V) kontrollerar om certifikatet (y) bekräftar att (x) tillhör språket (L). Formellt är ett språk (L) i NP om det finns en polynom-tidsalgoritm (V) och ett polynom (p(n)) så att det för varje sträng (x i L) finns en sträng (y) med ( |y|. lek p(|x|)) och (V(x, y) = 1). Omvänt, för varje sträng (x notin L), finns det ingen sträng (y) så att (V(x, y) = 1).
För att klargöra detta koncept, överväg det välkända problemet med "Boolean satisfiability" (SAT). SAT-problemet frågar om det finns en tilldelning av sanningsvärden till variabler i en given boolesk formel så att formeln utvärderas till sann. SAT-problemet finns i NP eftersom man, givet en boolesk formel ( phi ) och en tilldelning ( alfa ) av sanningsvärden till dess variabler, kan verifiera i polynomtid om (alfa) uppfyller ( phi ). Här är instansen ( x ) den booleska formeln ( phi ), och certifikatet ( y ) är tilldelningen ( alfa ). Verifieraren ( V ) kontrollerar om ( alfa ) gör ( phi ) sant, vilket kan göras i polynomtid med avseende på storleken på ( phi ).
Ett annat illustrativt exempel är problemet med "Hamiltonian Path". Detta problem frågar om det finns en väg i en given graf som besöker varje vertex exakt en gång. Hamiltonian Path-problemet finns också i NP eftersom man, givet en graf ( G ) och en sekvens av hörn ( P ), kan verifiera i polynomtid om ( P ) är en Hamiltonsk väg i ( G ). I det här fallet är instansen ( x ) grafen ( G ), och certifikatet ( y ) är sekvensen av hörn ( P ). Verifieraren (V) kontrollerar om (P) bildar en Hamiltonsk väg, vilket kan göras i polynomtid med avseende på storleken på (G).
Konceptet med polynom-tid-verifierbarhet är viktigt eftersom det ger ett sätt att karakterisera problem som är effektivt kontrollerbara, även om det kan vara beräkningsmässigt omöjligt att hitta lösningen. Detta leder till den berömda frågan om ( P = NP ), som frågar om varje problem vars lösning kan verifieras i polynomtid också kan lösas i polynomtid. Klassen ( P ) består av beslutsproblem som kan lösas i polynomtid av en deterministisk Turingmaskin. Om ( P = NP ), skulle det betyda att varje problem med en polynom-tidsverifierare också har en polynom-tidslösare. Denna fråga är fortfarande ett av de viktigaste öppna problemen inom datavetenskap.
En av nyckelegenskaperna hos NP är att den är stängd under polynomtidsreduktioner. En polynomtidsreduktion från ett språk (L_1) till ett språk (L_2) är en polynomtidsberäknbar funktion (f) så att (x i L_1) om och endast if (f(x) i L_2). Om det finns en polynomtidsreduktion från (L_1) till (L_2) och (L_2) är i NP, så är (L_1) också i NP. Denna egenskap är avgörande för studiet av NP-fullständighet, som identifierar de "svåraste" problemen i NP. Ett problem är NP-komplett om det är i NP och varje problem i NP kan reduceras till det i polynomtid. SAT-problemet var det första problemet som bevisats vara NP-komplett, och det fungerar som en grund för att bevisa NP-fullständigheten hos andra problem.
För att ytterligare illustrera konceptet med polynom-tidsverifierbarhet, överväg problemet med "Subset Summa". Detta problem frågar om det finns en delmängd av en given uppsättning heltal som summerar till ett specificerat målvärde. Subset Sum-problemet är i NP eftersom man, givet en uppsättning heltal ( S ), ett målvärde ( t ) och en delmängd ( S' ) av ( S ), kan verifiera i polynomtid om summan av elementen i (S') är lika med (t). Här är instansen (x) paret ((S,t)), och certifikatet (y) är delmängden (S'). Verifieraren (V) kontrollerar om summan av elementen i (S') är lika med (t), vilket kan göras i polynomtid med avseende på storleken på (S).
Vikten av polynom-tid-verifierbarhet sträcker sig bortom teoretiska överväganden. Rent praktiskt betyder det att för problem i NP, om en föreslagen lösning (certifikat) tillhandahålls, kan den kontrolleras effektivt. Detta har betydande konsekvenser för kryptografiska protokoll, optimeringsproblem och olika områden där det är viktigt att verifiera en lösnings korrekthet.
För att sammanfatta, omfattar klassen NP beslutsproblem för vilka en föreslagen lösning kan verifieras i polynomtid med en deterministisk algoritm. Detta koncept är grundläggande i beräkningskomplexitetsteori och har djupgående implikationer för både teoretiska och praktiska aspekter av datavetenskap. Studiet av NP, polynom-tidsverifierbarhet och relaterade begrepp som NP-fullständighet fortsätter att vara ett levande och kritiskt forskningsområde.
Andra senaste frågor och svar ang Komplexitet:
- Är PSPACE-klassen inte lika med EXPSPACE-klassen?
- Är P-komplexitetsklassen en delmängd av PSPACE-klassen?
- Kan vi bevisa att Np och P klass är samma genom att hitta en effektiv polynomlösning för alla NP kompletta problem på en deterministisk TM?
- Kan NP-klassen vara lika med EXPTIME-klassen?
- Finns det problem i PSPACE som det inte finns någon känd NP-algoritm för?
- Kan ett SAT-problem vara ett komplett NP-problem?
- Kan ett problem vara i NP-komplexitetsklass om det finns en icke deterministisk turingmaskin som löser det i polynomtid
- Är P och NP faktiskt samma komplexitetsklass?
- Är varje sammanhang fritt språk i P-komplexitetsklassen?
- Finns det en motsägelse mellan definitionen av NP som en klass av beslutsproblem med polynomtidsverifierare och det faktum att problem i klassen P också har polynomtidsverifierare?
Se fler frågor och svar i Complexity