PSPACE

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 polinomial (S(n) = a_{k} n^{k} + a_{k-1} n^{k-1} + \dots + a_{0} ) 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:

\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k)

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

Relación entre otras clases

Todos los problemas resolubles en tiempo polinómico con máquinas no deterministas (todos los problemas que están en NP) pueden resolverse en espacio polinómico, por lo tanto, PSPACE incluye 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, entonces PSPACE = NP, o si estuviera alguno de ellos en P, entonces PSPACE = P.

El conjunto PSPACE es un subconjunto estricto del conjunto de lenguajes sensitivos al contexto. Las siguientes inclusiones han sido demostradas:

NL ⊆ P ⊆ NP ⊆ PSPACE

NL ⊂ PSPACE ⊂ EXPSPACE

PSPACE-completo ⊆ PSPACE

En la primera línea hay tres inclusiones, y se sabe que 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 y 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.

Los problemas más difíciles en PSPACE son los del conjunto PSPACE-completo.

Otras características

Una característica alternativa de PSPACE es el conjunto de problemas decidibles por una máquina de Turing alternativa en tiempo polinomial, a veces llamadas APTIME o solamente AP.

Una característica lógica de PSPACE desde la teoría de la complejidad descriptiva es que son conjuntos de problemas expresados en segundo orden lógico con la adición de un operador de la clausura transitiva. Un cierre transitivo completo no es necesario; un cierre transitivo conmutativo es suficiente e incluso formas más débiles. La adicción de este operador hace distinguible el PSPACE del PH.

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. 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.


Wikimedia foundation. 2010.

См. также в других словарях:

  • PSPACE — Unsolved problems in computer science Is P = PSPACE ? PSPACE …   Wikipedia

  • PSPACE — In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können. Nach dem Satz von Savitch ist PSPACE gleich der Klasse NPSPACE, der… …   Deutsch Wikipedia

  • PSPACE — …   Википедия

  • PSPACE-completo — En teoría de la complejidad computacional, la clase de complejidad PSPACE completo (PSPACE complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los… …   Wikipedia Español

  • PSPACE-complete — Mathematicians and computer scientists try to carefully define different types of complexity, and PSPACE complete is one of these types.Roughly, PSPACE is all the problems which can be solved by programs which only need a polynomial (in the… …   Wikipedia

  • PSPACE-Vollständigkeit — In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können. Nach dem Satz von Savitch ist PSPACE gleich der Klasse NPSPACE, der… …   Deutsch Wikipedia

  • PSPACE-hard — In computational complexity theory, a decision problem p is said to be PSPACE hard if, given any decision problem q in PSPACE, q can be reduced to p in polynomial time. PSPACE hardness is distinguished from PSPACE completeness by the fact that… …   Wikipedia

  • Класс PSPACE — В теории сложности вычислений PSPACE набор всех проблем разрешимости, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства. Содержание 1 Машина Тьюринга с полиномиальным ограничением пространства …   Википедия

  • List of PSPACE-complete problems — Here are some of the more commonly known problems that are PSPACE complete when expressed as decision problems. This list is in no way comprehensive. Games and puzzles Generalized versions of: Amazons· Atomix· Geography· Gomoku· Hex· Reversi·… …   Wikipedia

  • IP (complexity) — In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Goldwasser, et al. in 1985. An interactive proof system consists …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»