PSPACE-completude

Em teoria da complexidade computacional, um problema de decisão é PSPACE-completo se pertence à classe de complexidade PSPACE e todos os problemas em PSPACE podem ser reduzidos a ele em tempo polinomial. Os problemas PSPACE-completos podem ser vistos como os problemas mais difíceis em PSPACE, porque uma solução para qualquer problema PSPACE-completo pode ser facilmente utilizada para resolver qualquer outro problema em PSPACE. Em geral, acredita-se que tais problemas não pertencem às famosas classes de complexidade P e NP, mas isso ainda é desconhecido. Sabe-se que eles estão fora da pequena classe de problemas NC, já que NC está contido em PolyL = DSPACE((log n)^O(1))), que está estritamente contido em PSPACE pelo teorema da hierarquia de espaço.

Discussão

O primeiro problema conhecido PSPACE-completo foi o problema de decisão para gramáticas determinística sensíveis ao contexto. No problema de decisão para gramáticas sensíveis ao contexto, é dado um conjunto de transformações gramaticais que podem aumentar, mas não diminuir, o comprimento de uma sentença, e visa determinar se uma dada sentença pode ser produzida por essas transformações. A condição técnica de "determinismo" (implicando, basicamente, que toda transformação deixa claro que ela foi utilizada) garante que esse processo é solúvel em espaço polinomial e o trabalho de S.-Y. Kuroda em 1964 "Classes de linguagens e autômatos linearmente limitados" mostrou que qualquer programa computável (possivelmente não-determinístico) em espaço linear pode ser convertido em análise sintática de gramáticas sensíveis ao contexto, de maneira a preservar o determinismo.

Em 1970, o teorema de Savitch mostrou que PSPACE é fechado sob não-determinismo, implicando que até gramáticas não-determinísticas sensíveis ao contexto estão em PSPACE.

Mas o problema arquetípico PSPACE-completo é geralmente considerado como sendo o problema da fórmula booleana completamente quantificada (usualmente abreviado para QBF ou TQBF), uma generalização do primeiro problema NP-completo conhecido, o problema da satisfatibilidade de fórmulas booleanas (SAT). O problema da satisfatibilidade é o problema de determinar se há valorações-verdade para variáveis que tornam uma expressão booleana verdadeira. Por exemplo, uma instância de SAT seria a questão de se determinar se a sentença seguinte é verdadeira:

$\exists x_{1}\,\exists x_{2}\,\exists x_{3}\,\exists x_{4}:(x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{2}\lor x_{3}\lor \neg x_{4})$

O problema de fórmulas booleanas quantificadas difere no sentido de que permite tanto o quantificador universal quanto o existencial sobre os valores das variáveis, como por exemplo:

$\exists x_{1}\,\forall x_{2}\,\exists x_{3}\,\forall x_{4}:(x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{2}\lor x_{3}\lor \neg x_{4})$.

A prova de que QBF é um problema PSPACE-completo é essencialmente uma reestruturação da prova do teorema de Savitch na linguagem da lógica, e é um pouco mais técnica.

Note que um problema NP-completo lembra um quebra-cabeças: há uma maneira de encaixar os valores para solucionar o problema? Os problemas PSPACE-completos lembram um jogo: há algum movimento que eu possa fazer de tal forma que, para todos os movimentos que meu oponente possa fazer, haverá algum outro movimento que eu possa fazer para vencer? Essa questão utiliza tanto quantificadores existenciais quanto universais. Não é surpresa que muitos quebra-cabeças se revelam NP-completos e muitos jogos se mostram PSPACE-completos.

Exemplos de jogos PSPACE-completos (quando generalizados de tal maneira que possam ser jogados num tabuleiro n × n) são os jogos Hex, Reversi, Mahjong, Atomix e Sokoban. Alguns outros jogos como xadrez, damas e Go são EXPTIME-completos porque um jogo entre dois jogadores perfeitos pode ser muito longo, então é improvável que estejam em PSPACE. Entretanto, eles se tornam PSPACE-completos se há um limite polinomial no número de movimentos.

Note que a definição de PSPACE-completude é baseada em uma complexidade assintótica: o tempo necessário para resolver um problema de tamanho n, com o limite sendo n, cresce sem limitações. Isso significa que jogos como damas (que é jogado num tabuleiro 8 × 8) nunca poderia ser PSPACE-completo (de fato, eles podem ser resolvidos em tempo e espaço constantes utilizando uma tabela de símbolos extremamente grande). Esse é o motivo pelo qual todos os jogos foram modificados para serem jogados em tabuleiros n × n.

Outro problema PSPACE-completo é o problema de se decidir se uma dada cadeia é membro de uma linguagem definida por uma gramática sensível ao contexto.

Exemplos de problemas PSPACE-completos

Os seguintes problemas PSPACE-completos serão mostrados junto com seus algoritmos demonstrando que estão em PSPACE.

TQBF

• Seja TQBF = { <F> : F é uma fórmula booleana verdadeira totalmente quantificada}. Sobre a entrada F:
  • Se F não tem quantificador, avalie e aceite se e somente se F é verdade.
  • Se F=$\forall$pF', avalie recursivamente F'[p=1] e F'[p=0], aceitando se somente se ambos aceitam.
  • Se F=$\exists$qF', avalie recursivamente F'[q=1], F'[q=0] e aceite se pelo menos um aceita.
• Utilização de espaço: o número de níveis de recursão é igual ao número de variáveis de F. A quantidade de informação armazenada em cada nível da recursão é constante (valores das fórmulas para p=0 e p=1). Consequentemente, o espaço total utilizado é linear.

Geografia generalizada

• Sobre a entrada <G,b>:
  • Se b não tem vértices de saída, rejeite.
  • Se tem, remova b e todas as suas arestas e chame esse novo grafo de G₁.
  • Rode recursivamente nas entradas <G₁,b_i>, em que cada b_i são vértices ligados por arestas a partir de b.
  • Rejeite se tudo for aceito. Se não, aceite.
• Utilização de espaço: o número de níveis de recursão é igual ao número de nós de G. A quantidade de informação armazenada em cada nível de recursão é igual ao número de nós de G. Consequentemente, o espaço total utilizado é linear.

Determinar se uma linguagem regular gera todas as cadeias

Dada uma expressão regular R, determinar se ela gera todas as cadeias (i.e., L(R) = Σ^*) é um problema PSPACE-completo.

Bibliografia

• Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X  Section 8.3: PSPACE-completeness, pp. 283–94.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. [S.l.]: W.H. Freeman. ISBN 0-7167-1045-5  Section 7.4: Polynomial Space Completeness, pp. 170–77.

Ligações externas

• «Computational Complexity of Games and Puzzles» 
• «Go/Baduk, Board game: "Ladders" work in this way»