Inom området för beräkningskomplexitetsteori, särskilt när man undersöker rymdkomplexitetsklasser, är förhållandet mellan PSPACE och NP av betydande intresse. För att ta upp frågan direkt: ja, det finns problem i PSPACE som det inte finns någon känd NP-algoritm för. Detta påstående har sina rötter i definitionerna och sambanden mellan dessa komplexitetsklasser.
PSPACE är klassen av beslutsproblem som kan lösas av en Turing-maskin som använder en polynommängd utrymme. Med andra ord, ett problem finns i PSPACE om det finns en algoritm som kan lösa det med en mängd minne som är polynom i storleken på ingången. Denna klass omfattar en mängd olika problem, av vilka några är ganska komplexa och involverar invecklade beräkningsprocesser.
NP, å andra sidan, är den klass av beslutsproblem för vilka en föreslagen lösning kan verifieras i polynomtid av en deterministisk Turing-maskin. Detta innebär att om någon ger dig en kandidatlösning på ett problem i NP, kan du snabbt kontrollera att den lösningen är korrekt, särskilt i polynomtid i förhållande till indatastorleken.
Relationen mellan dessa två klasser är sådan att NP är en delmängd av PSPACE. Detta beror på att alla problem som kan verifieras i polynomtid också kan lösas i polynomrymden. För att förstå varför, tänk på att en polynom-tidsverifierare endast kan läsa ett polynomantal bitar av ingången och den föreslagna lösningen. Därför kan den simuleras av en polynom-rymdmaskin som håller reda på positionerna den har läst och de operationer den har utfört.
Det omvända är dock inte känt för att vara sant; det är inte känt om PSPACE är en delmängd av NP. Det är faktiskt en allmän uppfattning att PSPACE innehåller problem som inte finns i NP, även om detta inte har bevisats formellt. Denna uppfattning är baserad på att det finns problem i PSPACE som verkar kräva mer än polynomtid att lösa, även om de kan lösas med polynomutrymme.
Ett av de kanoniska exemplen på ett problem i PSPACE som inte är känt för att finnas i NP är problemet med Quantified Boolean Formula (QBF). QBF är en generalisering av Boolean satisfiability problem (SAT), som är NP-komplett. Medan SAT frågar om det finns en tilldelning av sanningsvärden till variabler som gör en given boolesk formel sann, involverar QBF kapslade kvantifierare över variablerna, såsom "för alla x, det finns ay så att formeln är sann." Närvaron av dessa kvantifierare gör QBF betydligt mer komplex. QBF är PSPACE-komplett, vilket betyder att det är lika svårt som alla problem i PSPACE. Om det fanns en NP-algoritm för QBF skulle det innebära att NP är lika med PSPACE, ett resultat som skulle vara banbrytande och anses allmänt osannolikt.
Ett annat illustrativt exempel är problemet med att avgöra vinnaren i generaliserade spel, såsom generaliserade versioner av schack eller Go, som spelas på ett N x N-bräde. Dessa problem involverar ett potentiellt exponentiellt antal drag och konfigurationer, men de kan avgöras med polynomrymden genom att systematiskt utforska alla möjliga speltillstånd. Dessa problem är också PSPACE-kompletta, vilket ytterligare tyder på att det finns problem i PSPACE som inte finns i NP.
För att gräva djupare in i varför vissa problem i PSPACE tros ligga utanför NP, överväg karaktären av rymdbegränsade kontra tidsgränsade beräkningar. Polynomutrymme tillåter ett potentiellt exponentiellt antal beräkningssteg, så länge som det använda utrymmet förblir polynomiellt begränsat. Detta står i skarp kontrast till NP, där tiden är polynomiellt begränsad. Den exponentiella tid som tillåts av polynomutrymme kan användas för att lösa problem som involverar uttömmande sökningar över exponentiellt stora utrymmen, såsom de som påträffas i QBF och generaliserade spel.
Dessutom finns det intrikata teoretiska konstruktioner som ytterligare stödjer distinktionen mellan PSPACE och NP. Till exempel, begreppet alternering, introducerat av Chandra, Kozen och Stockmeyer, generaliserar icke-determinism och leder till klassen AP (alternerande polynomtid). Det har visats att AP är lika med PSPACE, vilket ger ett annat perspektiv på kraften i polynomiska rymdberäkningar. Alternering involverar en sekvens av existentiella och universella kvantifierare, som speglar strukturen hos QBF, och visar upp komplexiteten som är inneboende i PSPACE-problem.
Det är också värt att notera att separationen av komplexitetsklasser är en grundläggande öppen fråga inom teoretisk datavetenskap. Det berömda P vs NP-problemet är ett specialfall av denna bredare undersökning. På samma sätt förblir frågan om NP är lika med PSPACE olöst. Emellertid är konsensus inom området, baserat på omfattande studier och arten av kända problem, att PSPACE sannolikt innehåller problem som inte finns i NP.
Förekomsten av problem i PSPACE för vilka det inte finns någon känd NP-algoritm stöds av definitionerna och sambanden mellan dessa komplexitetsklasser, såväl som av konkreta exempel som QBF och generaliserade spelproblem. Dessa exempel belyser de invecklade och potentiellt exponentiella beräkningsprocesserna som kan hanteras inom polynomrymden men som sannolikt inte kommer att begränsas till polynomtid, vilket placerar dem utanför NP:s områ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?
- 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
- 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