Kan ett problem vara i NP-komplexitetsklass om det finns en icke deterministisk turingmaskin som löser det i polynomtid
Frågan "Kan ett problem vara i NP-komplexitetsklass om det finns en icke-deterministisk Turing-maskin som kommer att lösa det i polynomtid?" berör grundläggande begrepp inom beräkningskomplexitetsteori. För att ta itu med denna fråga på ett heltäckande sätt måste vi överväga definitionerna och egenskaperna hos NP-komplexitetsklassen och rollen för icke-deterministiska Turing-maskiner (NDTM).
Definition av NP
Klassen NP (icke-deterministisk polynomtid) består av beslutsproblem för vilka en given lösning kan verifieras som korrekt eller felaktig i polynomtid av en deterministisk Turing-maskin (DTM). Formellt är ett beslutsproblem i NP om det finns en polynom-tidsverifieringsalgoritm som kan verifiera riktigheten av ett givet certifikat (eller vittne) för en instans av problemet.
Icke-deterministiska Turing-maskiner
En icke-deterministisk Turing-maskin är en teoretisk beräkningsmodell som utökar kapaciteten hos en deterministisk Turing-maskin. Till skillnad från en DTM, som följer en enda beräkningsväg definierad av dess övergångsfunktion, kan en NDTM följa flera beräkningsvägar samtidigt. Vid varje steg kan en NDTM "välja" från en uppsättning möjliga övergångar, och effektivt utforska många möjliga beräkningar parallellt.
Polynom-tidslöslighet av NDTM
Ett problem sägs vara lösbart av en NDTM i polynomtid om det finns en icke-deterministisk algoritm som kan hitta en lösning på problemet inom ett antal steg som är polynom i storleken på inmatningen. Detta betyder att NDTM kan utforska en beräkningsväg som leder till en lösning i polynomtid för varje instans av problemet.
Förhållandet mellan NP och NDTM
Klassen NP kan definieras ekvivalent i termer av NDTM. Specifikt är ett beslutsproblem i NP om och bara om det finns en NDTM som kan lösa problemet i polynomtid. Denna ekvivalens uppstår från det faktum att en NDTM kan gissa ett certifikat icke-deterministiskt och sedan verifiera det deterministiskt i polynomtid.
För att illustrera detta med ett exempel, överväg det välkända NP-kompletta problemet, det booleska tillfredsställelsesproblemet (SAT). Givet en boolesk formel i konjunktiv normalform (CNF) är uppgiften att avgöra om det finns en tilldelning av sanningsvärden till variablerna som gör formeln sann. En NDTM kan lösa SAT i polynomtid genom att icke-deterministiskt gissa en tilldelning av sanningsvärden och sedan deterministiskt kontrollera om tilldelningen uppfyller formeln. Verifieringssteget, som innebär att utvärdera formeln under den gissade uppgiften, kan göras i polynomtid.
Implikationer av Polynom-Time Solvability av NDTMs
Med tanke på ovanstående definitioner och ekvivalensen mellan NP och polynomtidslöslighet med NDTM:er kan vi dra slutsatsen att om det finns en NDTM som löser ett problem i polynomtid, så är problemet verkligen i NP. Detta beror på att förekomsten av en sådan NDTM innebär att det finns en polynom-tidsverifieringsalgoritm för problemet. Den icke-deterministiska gissningsfasen av NDTM:n motsvarar genereringen av ett certifikat, och den deterministiska verifieringsfasen motsvarar polynom-tidsverifieringsalgoritmen.
Ytterligare överväganden och exempel
För att ytterligare belysa detta koncept, låt oss överväga ytterligare exempel på problem i NP och deras förhållande till NDTM:
1. Hamiltons vägproblem: Givet en graf frågar Hamiltonian Path-problemet om det finns en väg som besöker varje vertex exakt en gång. En NDTM kan lösa detta problem i polynomtid genom att icke-deterministiskt gissa en sekvens av hörn och sedan verifiera om sekvensen bildar en giltig Hamiltonsk väg. Verifieringssteget innebär att kontrollera närliggande hörn i följd och säkerställa att varje hörn besöks exakt en gång, vilket båda kan göras i polynomtid.
2. Delmängd Summa Problem: Givet en uppsättning heltal och en målsumma, frågar Subset Sum-problemet om det finns en delmängd av heltal som summerar till målet. En NDTM kan lösa detta problem i polynomtid genom att icke-deterministiskt gissa en delmängd av heltalen och sedan verifiera om summan av delmängden är lika med målet. Verifieringssteget innefattar summering av elementen i den gissade delmängden, vilket kan göras i polynomtid.
3. Graffärgningsproblem: Med tanke på en graf och ett antal färger, frågar problemet med graffärgning om det är möjligt att färglägga grafens hörn så att inte två närliggande hörn delar samma färg. En NDTM kan lösa detta problem i polynomtid genom att icke-deterministiskt tilldela färger till hörnen och sedan verifiera om färgningen är giltig. Verifieringssteget innefattar kontroll av färgerna på intilliggande hörn, vilket kan göras i polynomtid.
Slutsats
I ljuset av definitionerna och exemplen som tillhandahålls är det tydligt att ett problem verkligen kan vara i NP-komplexitetsklassen om det finns en icke-deterministisk Turing-maskin som kommer att lösa det i polynomtid. Detta förhållande är en hörnsten i beräkningskomplexitetsteorin och understryker ekvivalensen mellan polynom-tidslöslighet av NDTM och medlemskap i NP-klassen.
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?
- NP är klassen av språk som har polynomiska tidsverifierare
- Ä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