PSPACE

En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio de polinomios () y tiempo ilimitado.

La definición no depende del carácter determinista de la máquina de Turing (esto es un corolario del teorema de Savitch). De manera que PSPACE = NPSPACE. Si un problema se resuelve mediante un algoritmo no determinista de complejidad espacial polinómica, también se puede resolver mediante un algoritmo determinista de complejidad espacial polinómica.

Definición formal

En el caso de la complejidad espacial, se puede caracterizar la clase de lenguajes PSPACE:

es decir, la unión de todas las clases de complejidad espacial polinómicas sobre Máquinas de Turing deterministas.

Other Languages
العربية: بيسبايس
Deutsch: PSPACE
English: PSPACE
français: PSPACE
עברית: PSPACE
italiano: PSPACE
日本語: PSPACE
한국어: PSPACE
Nederlands: PSPACE
português: PSPACE
русский: Класс PSPACE
српски / srpski: PSPACE
Tiếng Việt: PSPACE
中文: PSPACE