Diferencia entre revisiones de «PSPACE»

Todos los problemas resolubles en tiempo polinómico con máquinas no deterministas (todos los problemas que están en [[NP (clase de complejidad)|NP]]) pueden resolverse en espacio polinómico, por lo tanto, '''PSPACE''' incluye [[NP (clase de complejidad)|NP]] y [[Co-NP]].

Se conjetura que exista un conjunto de problemas que sean [[PSPACE-completo]]. Si lo hubiera y uno de ellos estuviera en [[NP (clase de complejidad)|NP]], entonces '''PSPACE = NP''', o si estuviera alguno de ellos en [[P (clase de complejidad)|P]], entonces '''PSPACE = P'''.

En la primera línea hay tres inclusiones, y se sabe que [[NL (clase de complejidad)|NL]] ⊂ PSPACE, de manera que al menos una de las inclusiones es estricta, aunque se ha descubierto cuál de ellas lo es. Se sospecha que las tres son inclusiones estrictas. Una solución al problema de saber si las clases [[P (clase de complejidad)|P]] y [[NP (clase de complejidad)|NP]] son distintas vale un millón de dólares. Se sospecha también que la inclusión de la última línea es estricta.

Un importante resultado de la teoría de la complejidad es que '''PSPACE''' puede ser caracterizada como todas las lenguas reconocidas por la presencia de un sistema interactivo de la prueba (interactive proof system), una definición de la clase '''[[IP''' (clase de complejidad)|IP]]. En este sistema, hay una demostración que intenta convencer aleatoriamente en [[tiempo polinomial]] para verificar que una cadena pertenece al lenguaje. Debe ser capaz de convencer al verificador con una elevada probabilidad, si la cadena está en el lenguaje, pero no debería ser capaz de convencer con una baja probabilidad, si la cadena no está en el lenguaje.