Mostrar código-fonte de PSPACE-completude

{{Mais notas|data=julho de 2016}}
{{Reciclagem|data=julho de 2011}}
Em [[Complexidade computacional|teoria da complexidade computacional]], um [[problema de decisão]] é '''PSPACE-completo''' se pertence à [[Classes de Complexidade|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 (complexidade)|P]]''' e '''[[NP (complexidade)|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'')<sup>O(1)</sup>)), 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 [[Máquina de estados finitos determinística|determinística]] [[Gramática sensível ao contexto|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"<ref>"Classes of languages and linear-bounded automata", [[Information and Control]], 7(2): 207–223, June 1964</ref> mostrou que qualquer programa computável (possivelmente não-determinístico) em [[Espaço vetorial|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 [[Problema de satisfatibilidade booleana|(SAT)]]. O problema da satisfatibilidade é o problema de determinar se há [[Valor de verdade|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:
: <math>\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)</math>

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:
: <math>\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)</math>.
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'' &times; ''n'') são os jogos [[Hex (jogo)|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 &times; 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'' &times; ''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=<math>\forall</math>pF', avalie recursivamente F'[p=1] e F'[p=0], aceitando se somente se ambos aceitam.
** Se F=<math>\exist</math>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.<ref name="fpitt">{{Citar web| título = Lecture Summary for Week 11 work| autor = François Pitt| url = http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt| acessodata = 2008-02-12| arquivourl = https://web.archive.org/web/20110607195631/http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt| arquivodata = 2011-06-07| urlmorta = yes}}</ref>

=== 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<sub>1</sub>.
** Rode recursivamente nas entradas <G<sub>1</sub>,b<sub>i</sub>>, em que cada b<sub>i</sub> 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.<ref name="fpitt" />

=== 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'') = Σ<sup>*</sup>) é um problema PSPACE-completo.

{{referencias}}

== Bibliografia ==
* {{citar livro|autor = Michael Sipser |ano= 1997 |título= Introduction to the Theory of Computation |publicado= PWS Publishing | isbn = 0-534-94728-X |autorlink = Michael Sipser}} Section 8.3: PSPACE-completeness, pp.&nbsp;283–94.
* {{citar livro|autor = [[Michael R. Garey]] and [[David S. Johnson]] |ano= 1979 |título= [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] |publicado= W.H. Freeman | isbn = 0-7167-1045-5}} Section 7.4: Polynomial Space Completeness, pp.&nbsp;170–77.
{{Reflist}}

== Ligações externas ==
* {{Link||2=http://www.ics.uci.edu/~eppstein/cgt/hard.html |3=Computational Complexity of Games and Puzzles}}
* {{Link||2=http://senseis.xmp.net/?path=Tesuji&page=Ladder |3=Go/Baduk, Board game: "Ladders" work in this way}}

{{Classes de complexidade}}
{{DEFAULTSORT:Pspace Completude}}
[[Categoria:Classes de complexidade]]