PSPACE

Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço.

Definição Formal

Se denotamos por SPACE ( t ( n )) , o conjunto de todos os problemas que podem ser resolvidos por máquinas de Turing usando no máximo t ( n ) espaço para alguma função t do tamanho da entrada n , então podemos definir PSPACE formalmente como

${\mbox{PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{SPACE}}(n^{k})$

PSPACE é um superconjunto estrito do conjunto de linguagens sensíveis ao contexto .

Acontece que permitir a máquina de Turing ser não-determinística, não adiciona nenhum poder extra. Por causa do Teorema de Savitch , NPSPACE é equivalente a PSPACE, essencialmente porque uma máquina de Turing determinística pode simular uma máquina de Turing não determinística sem precisar de muito mais espaço (mesmo que ela possa usar muito mais tempo). Além disso, o complemento de todos os problemas em PSPACE também estão em PSPACE, o que significa que Co-PSPACE = PSPACE.

Relação entre outras classes

A representação da relação entre classes de complexidade

As seguintes relações são conhecidas entre PSPACE e as Classes de Complexidade NL , P, NP, PH , EXPTIME e EXPSPACE:

${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PH}}\subseteq {\mbox{PSPACE}}$

${\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}\subseteq {\mbox{EXPSPACE}}$

${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$

É conhecido que na primeira e na segunda linha, pelo menos uma das inclusões devem ser estritas, mas não se sabe qual. Suspeita-se que todas são estritas. Um trabalho recente de L. Gordeev e E. H. Haeusler demonstrou que NP = CoNP = PSPACE através da compressão de provas em Dedução Natural na Lógica Minimal Implicacional.

Em outras palavras, as inclusões na terceira linha são conhecidas como estritas. A primeira resulta da diagonalização direta (o teorema de hierarquia do espaço, ${\mbox{NL}}\subsetneq {\mbox{NPSPACE}}$) e o fato de que ${\mbox{PSPACE}}={\mbox{NPSPACE}}$ pelo Teorema de Savitch. O segundo segue simplesmente o teorema de hierarquia espacial.

Os problemas mais difíceis em PSPACE são os problemas PSPACE-Completos.

Outras caracterizações

Uma caracterização alternativa de PSPACE é o conjunto de problemas decidíveis por uma máquina de Turing alternante em tempo polinomial, às vezes chamado APTIME, ou apenas AP.

A caracterização lógica de PSPACE da teoria da complexidade descritiva é que ela é o conjunto de problemas expressivos em lógica de segunda ordem com a adição de um operador de fechamento transitivo. Um fechamento total transitivo não é necessário; um fechamento comutativo transitivo e formas ainda mais fracas satisfazem. É a adição deste operador que (possivelmente) distingue PSPACE de PH.

Um resultado importante da teoria da complexidade é que PSPACE pode ser caracterizado como todas as línguas reconhecidas por um sistema de prova interativa em particular, o que define a classe IP . Nesse sistema, há um poderoso provador tentando convencer um verificador de tempo polinomial aleatório que uma cadeia pertence a linguagem. Isso deve ser capaz de convencer o verificador com alta probabilidade se a cadeia pertence a linguagem, mas não deve ser capaz de convencê-lo, a não ser com baixa probabilidade, se a cadeia não pertence a linguagem.

PSPACE pode ser caracterizada como a classe de complexidade quântica QIP.

PSPACE-completude

Uma linguagem B é PSPACE-completo se ele estiver em PSPACE e é PSPACE-difícil, o que significa que para todo A $\in$ PSPACE, A $\leq _{p}$ B, onde A $\leq _{p}$ B significa que há uma redução em tempo polinomial de A para B. Problemas PSPACE-completo são de grande importância ao estudo dos problemas PSPACE porque eles representam os problemas mais difíceis em PSPACE. Encontrar uma solução simples para um problema PSPACE-completo significa que temos uma solução simples para todos os outros problemas em PSPACE porque todos os problemas PSPACE poderiam ser reduzidos a um problema PSPACE-completo. Um problema pode ser PSPACE-difícil, mas não PSPACE-completo porque pode não estar em PSPACE.
Por exemplo, o Problema da parada é PSPACE-difícil, mas não PSPACE-completo.