En l'àmbit de la teoria de la complexitat computacional, especialment quan s'examinen les classes de complexitat espacial, la relació entre PSPACE i NP té un interès important. Per abordar la pregunta directament: sí, hi ha problemes a PSPACE per als quals no es coneix un algorisme NP. Aquesta afirmació està arrelada en les definicions i les relacions entre aquestes classes de complexitat.
PSPACE és la classe de problemes de decisió que es poden resoldre amb una màquina de Turing utilitzant una quantitat d'espai polinomial. En altres paraules, un problema és a PSPACE si existeix un algorisme que el pugui resoldre utilitzant una quantitat de memòria polinomial en la mida de l'entrada. Aquesta classe abasta una gran varietat de problemes, alguns dels quals són força complexos i impliquen processos computacionals complexos.
NP, d'altra banda, és la classe de problemes de decisió per als quals una solució proposada pot ser verificada en temps polinomial per una màquina de Turing determinista. Això vol dir que si algú us proporciona una solució candidata a un problema en NP, podeu comprovar la correcció d'aquesta solució ràpidament, específicament en temps polinomi en relació amb la mida d'entrada.
La relació entre aquestes dues classes és tal que NP és un subconjunt de PSPACE. Això és degut a que qualsevol problema que es pugui verificar en temps polinomial també es pot resoldre en espai polinomial. Per entendre per què, considereu que un verificador de temps polinomial només pot llegir un nombre polinomial de bits de l'entrada i la solució proposada. Per tant, pot ser simulat per una màquina d'espai polinomial que fa un seguiment de les posicions que ha llegit i de les operacions que ha realitzat.
Tanmateix, no se sap que el contrari sigui cert; és a dir, no se sap si PSPACE és un subconjunt de NP. De fet, es creu àmpliament que PSPACE conté problemes que no es troben a NP, encara que això no s'ha demostrat formalment. Aquesta creença es basa en l'existència de problemes a PSPACE que sembla que requereixen més que un temps polinomial per resoldre, tot i que es poden resoldre amb espai polinomial.
Un dels exemples canònics d'un problema a PSPACE que no se sap que està en NP és el problema de la fórmula booleana quantificada (QBF). QBF és una generalització del problema de satisfacció booleà (SAT), que és NP-complet. Mentre que SAT pregunta si existeix una assignació de valors de veritat a variables que fa que una fórmula booleana determinada sigui certa, QBF implica quantificadors imbricats sobre les variables, com ara "per a totes les x, hi ha alguna tal que la fórmula sigui certa". La presència d'aquests quantificadors fa que el QBF sigui significativament més complex. QBF és PSPACE complet, és a dir, és tan difícil com qualsevol problema a PSPACE. Si hi hagués un algorisme NP per a QBF, implicaria que NP és igual a PSPACE, un resultat que seria innovador i que es considera poc probable.
Un altre exemple il·lustratiu és el problema de determinar el guanyador en jocs generalitzats, com les versions generalitzades d'escacs o Go, jugades en un tauler N x N. Aquests problemes impliquen un nombre potencialment exponencial de moviments i configuracions, però es poden decidir utilitzant l'espai polinomial explorant tots els estats de joc possibles de manera sistemàtica. Aquests problemes també són complets de PSPACE, cosa que suggereix a més l'existència de problemes a PSPACE que no estan a NP.
Per aprofundir en per què es creu que determinats problemes de PSPACE estan fora de NP, considereu la naturalesa dels càlculs delimitats per l'espai versus el temps limitat. L'espai polinomial permet un nombre potencialment exponencial de passos computacionals, sempre que l'espai utilitzat es mantingui acotat polinomialment. Això està en fort contrast amb NP, on el temps està limitat polinomialment. El temps exponencial que permet l'espai polinomial es pot utilitzar per resoldre problemes que impliquen cerques exhaustives en espais exponencialment grans, com els que es troben en QBF i jocs generalitzats.
A més, hi ha construccions teòriques complexes que donen suport a la distinció entre PSPACE i NP. Per exemple, el concepte d'alternança, introduït per Chandra, Kozen i Stockmeyer, generalitza el no determinisme i condueix a la classe AP (temps polinomi alternant). S'ha demostrat que AP és igual a PSPACE, proporcionant així una perspectiva diferent sobre la potència dels càlculs de l'espai polinomial. L'alternança implica una seqüència de quantificadors existencials i universals, que reflecteixen l'estructura de QBF i mostra la complexitat inherent als problemes de PSPACE.
També val la pena assenyalar que la separació de classes de complexitat és una qüestió oberta fonamental en la informàtica teòrica. El famós problema P vs NP és un cas especial d'aquesta investigació més àmplia. De la mateixa manera, la qüestió de si NP és igual a PSPACE continua sense resoldre's. Tanmateix, el consens en el camp, basat en un estudi extens i en la naturalesa dels problemes coneguts, és que PSPACE probablement conté problemes que no es troben a NP.
L'existència de problemes a PSPACE per als quals no es coneix un algorisme NP està recolzada per les definicions i relacions entre aquestes classes de complexitat, així com per exemples concrets com QBF i problemes de joc generalitzats. Aquests exemples posen de manifest els processos computacionals complexos i potencialment exponencials que es poden gestionar dins de l'espai polinomial, però és poc probable que es limitin al temps polinomial, col·locant-los així fora de l'àmbit de NP.
Altres preguntes i respostes recents sobre Complexitat:
- La classe PSPACE no és igual a la classe EXPSPACE?
- La classe de complexitat P és un subconjunt de la classe PSPACE?
- Podem demostrar que les classes Np i P són iguals trobant una solució polinomial eficient per a qualsevol problema NP complet en un TM determinista?
- La classe NP pot ser igual a la classe EXPTIME?
- Un problema SAT pot ser un problema NP complet?
- Pot un problema estar en classe de complexitat NP si hi ha una màquina de tornejat no determinista que el resolgui en temps polinomial
- NP és la classe de llenguatges que tenen verificadors de temps polinomials
- P i NP són realment la mateixa classe de complexitat?
- És cada llenguatge lliure de context a la classe de complexitat P?
- Hi ha una contradicció entre la definició de NP com a classe de problemes de decisió amb verificadors de temps polinomial i el fet que els problemes de la classe P també tinguin verificadors de temps polinomial?
Veure més preguntes i respostes a Complexity