¿Cuáles son algunos buenos ejemplos de problemas computacionales que naturalmente caen en NPSPACE?

Entonces, resulta que PSPACE = NPSPACE. Mi profesor de complejidad lo describió como que la memoria es “más poderosa” que la computación porque puedes reutilizar la memoria.

Esto significa que cualquier ejemplo que tome NP-space puede hacerse solo en un espacio polinomial .

Recuerde exactamente lo que significa NP: es un tiempo polinomial no determinista . El no determinismo significa ser capaz de “ramificar” su computación un número arbitrario de veces a medida que avanza, ejecutando todo en paralelo. NP es la clase de problemas de decisión que tomaría tiempo polinómico en una máquina que podría ramificarse así.

Puede pasar trivialmente de una máquina de Turing no determinista a una determinista simplemente ejecutando cada “rama” secuencialmente. Pero dado que el número de “ramas” puede aumentar en cada paso, esto termina funcionando en un tiempo exponencial.

NPSPACE, de manera análoga, es la clase de problemas de decisión que puede resolver una máquina de Turing no determinista en el espacio polinomial. Sin embargo, resulta que simular una máquina de Turing no determinista en una máquina determinista solo requiere una cantidad de polinomios más espacio . De hecho, el uso del espacio es como máximo cuadrado. Este resultado, que muestra trivialmente que PSPACE = NPSPACE se llama teorema de Savitch.

No recuerdo todos los detalles de la demostración del teorema. La forma más sencilla de simular una máquina Turing no determinista con más espacio de manera eficiente es hacer una rama a la vez, reutilizando la memoria intermedia. Sin embargo, esto todavía requiere un índice que indique qué rama somos uno, que ocupa la memoria exponencial en sí.

El truco con el teorema de Savitch es encontrar una forma de verificar si podemos pasar de un estado a otro en la máquina en el espacio logarítmico . Esto nos permite hacer un seguimiento de en qué rama estamos en tiempo polinómico. El algoritmo real y más detalles se presentan bien en estas diapositivas que encontré en línea, y soy demasiado vago para escribirlo aquí: P.

Antes de tratar de entender NPSPACE, creo que deberías observar un punto fundamental.

Todos los ejemplos que mencionó son cosas específicas con parámetros específicos. El árbol completo del juego del ajedrez es un objeto finito y específico que puede almacenarse en tal y tal terabyte.

Lo mismo es cierto para la cantidad de composiciones musicales de un minuto. De hecho, dado que una pieza de música estéreo de 1 minuto puede representarse con mucha precisión mediante un archivo de aproximadamente 100 millones de bits, puede empaquetar * todas * tales composiciones en un espacio de tamaño [matemático] 2 ^ {100,000,000} [/ matemáticas] bits.

Ahora puedes discutir, ¡ahí! ¡Ahí mismo, aquí está el exponente que hace que esta cosa ocupe un espacio no polinómico! Bueno, sí, es cierto, pero antes que nada “NPSPACE” no es un acrónimo de “espacio no polinomial”, y en segundo lugar, [matemáticas] 2 ^ {100,000,000} [/ matemáticas] es solo un número fijo y finito . No se “comporta exponencialmente”, es solo una constante, que encontramos más fácil de expresar como exponente, pero también podríamos haberlo escrito en notación decimal si tuviéramos mucho papel.

Por supuesto, la declaración se vuelve más significativa si pregunta sobre el espacio requerido para almacenar todas las piezas de música de duración n segundos. Ahora, la observación que hicimos puede expresarse diciendo que, salvo cualquier método de compresión inteligente, el tamaño requerido para almacenar todas estas composiciones crece exponencialmente con n . Ahora tiene una declaración real sobre espacios de almacenamiento de tamaño exponencial.

Pero de nuevo: esto no es NPSPACE. NPSPACE es un conjunto de problemas de decisión que puede ser resuelto por una computadora no determinista que requiere un espacio de tamaño que es una potencia del tamaño del problema. Almacenar música o átomos no es un problema de decisión.

De hecho, el espacio requerido para almacenar “N átomos”, sea lo que sea “almacenar un átomo” puede ser lineal en N. Nada exponencial aquí. Mencionar que hay 10 ^ 80 átomos en el universo no hace que el problema de almacenamiento sea más difícil, solo dice que hay muchas cosas que deben almacenarse, y necesitará un almacenamiento de tamaño comparable.