PSPACE completo - PSPACE-complete

Na teoria da complexidade computacional , um problema de decisão é PSPACE-completo se puder ser resolvido usando uma quantidade de memória que é polinomial no comprimento de entrada ( espaço polinomial ) e se todos os outros problemas que podem ser resolvidos no espaço polinomial podem ser transformados nele em tempo polinomial . Os problemas que são PSPACE-completos podem ser considerados os problemas mais difíceis em PSPACE , a classe de problemas de decisão solucionáveis ​​no espaço polinomial, porque uma solução para qualquer um desses problemas poderia facilmente ser usada para resolver qualquer outro problema em PSPACE.

Os problemas conhecidos por serem PSPACE-completos incluem determinar propriedades de expressões regulares e gramáticas sensíveis ao contexto , determinar a verdade de fórmulas booleanas quantificadas , mudanças passo a passo entre soluções de problemas de otimização combinatória e muitos quebra-cabeças e jogos.

Teoria

Um problema é definido como PSPACE-completo se puder ser resolvido usando uma quantidade polinomial de memória (ele pertence a PSPACE) e todo problema em PSPACE pode ser transformado em tempo polinomial em uma instância equivalente do problema dado.

Os problemas PSPACE-completos são amplamente suspeitos de estarem fora das classes de complexidade mais famosas P (tempo polinomial) e NP (tempo polinomial não determinístico), mas isso não é conhecido. Sabe-se que eles estão fora da classe NC , uma classe de problemas com algoritmos paralelos altamente eficientes , pois problemas em NC podem ser resolvidos em uma quantidade de espaço polinomial no logaritmo do tamanho da entrada, e na classe de problemas solucionáveis ​​em essa pequena quantidade de espaço está estritamente contida em PSPACE pelo teorema da hierarquia espacial .

As transformações que geralmente são consideradas na definição da completude PSPACE são reduções muitos-um em tempo polinomial , transformações que transformam uma única instância de um problema de um tipo em uma única instância equivalente de um problema de um tipo diferente. No entanto, também é possível definir completude usando reduções de Turing , nas quais um problema pode ser resolvido em um número polinomial de chamadas a uma sub-rotina para o outro problema. Não se sabe se esses dois tipos de reduções levam a classes diferentes de problemas PSPACE-completo. Outros tipos de reduções, como reduções muitos-um que sempre aumentam o comprimento da entrada transformada, também foram considerados.

A versão da conjectura Berman-Hartmanis para conjuntos de estados PSPACE-completos que todos esses conjuntos são parecidos, no sentido de que todos eles podem ser transformado em outro por de tempo polinomial bijeções .

Exemplos

Linguagens formais

Dada uma expressão regular , determinar se ela gera todas as strings em seu alfabeto é PSPACE completo. ${\displaystyle R}$

O primeiro problema PSPACE completo conhecido foi o problema de palavras para gramáticas determinísticas sensíveis ao contexto . No problema de palavras para gramáticas sensíveis ao contexto, é dado um conjunto de transformações gramaticais que podem aumentar, mas não podem diminuir, o comprimento de uma frase, e deseja determinar se uma determinada frase poderia ser produzida por essas transformações. A condição técnica de "determinismo" (o que implica aproximadamente que cada transformação torna óbvio que foi utilizado) garante que este processo pode ser resolvido no espaço polinomial, e Kuroda (1964) mostrou que a cada (possivelmente não-determinístico) computável programa linear o espaço pode ser convertido na análise de uma gramática sensível ao contexto, de uma forma que preserva o determinismo. Em 1970, o teorema de Savitch mostrou que PSPACE é fechado sob não determinismo, implicando que mesmo gramáticas não determinísticas sensíveis ao contexto estão em PSPACE.

Lógica

Um problema padrão do PSPACE completo, usado em muitos outros resultados do PSPACE completo, é o problema da fórmula booleana quantificada , uma generalização do problema de satisfatibilidade booleana . O problema da fórmula booleana quantificada toma como entrada uma expressão booleana, com todas as suas variáveis ​​quantificadas universal ou existencialmente, por exemplo:

A saída do problema é o valor da expressão quantificada. Encontrar esse valor é PSPACE completo.

Reconfiguraçao

Os problemas de reconfiguração dizem respeito à conectividade de um espaço de estados de soluções para um problema combinatório. Por exemplo, testar se duas cores de 4 de um gráfico podem ser conectadas entre si por movimentos que mudam a cor de um vértice por vez, mantendo em cada etapa uma 4 cores válidas, é PSPACE completo, embora o mesmo O problema das 3 cores pode ser resolvido em tempo polinomial. Outra família de problemas de reconfiguração, usada de forma semelhante a fórmulas booleanas quantificadas como base para provas de completude PSPACE de muitos outros problemas nesta área, envolve lógica de restrição não determinística , na qual os estados são orientações de um grafo de restrição sujeito a certas restrições sobre quantos as arestas devem ser orientadas para dentro em cada vértice, e em que o movimento de um estado para outro inverte a orientação de uma única aresta.

Quebra-cabeças e jogos

O problema da fórmula booleana quantificada pode ser interpretado como um jogo por dois jogadores, um verificador e um falsificador. Os jogadores realizam jogadas que preenchem valores para as variáveis ​​quantificadas, na ordem em que são aninhadas, com o verificador preenchendo variáveis ​​quantificadas existencialmente e o falsificador preenchendo variáveis ​​universalmente quantificadas; o jogo é ganho pelo verificador se a fórmula preenchida se tornar verdadeira e pelo falsificador, caso contrário. Uma fórmula quantificada é verdadeira se e somente se o verificador tiver uma estratégia vencedora. Da mesma forma, o problema de determinar o vencedor ou perdedor de muitos outros jogos combinatórios acaba sendo PSPACE completo. Exemplos de jogos completos para PSPACE (quando generalizados para que possam ser jogados em um tabuleiro) são os jogos Hex e Reversi . Alguns outros jogos generalizados, como xadrez , damas (rascunhos) e Go estão completos em EXPTIME porque um jogo entre dois jogadores perfeitos pode ser muito longo, então é improvável que eles estejam no PSPACE. Mas eles se tornarão PSPACE-completos se um limite polinomial no número de movimentos for aplicado. ${\displaystyle n\times n}$

Também é possível que os quebra-cabeças jogados por um único jogador sejam completos no PSPACE. Freqüentemente, eles podem ser interpretados como problemas de reconfiguração e incluem os jogos de paciência Rush Hour , Mahjong , Atomix e Sokoban , e o computador mecânico Turing Tumble .

A completude do PSPACE é baseada na complexidade em função do tamanho da entrada , no limite conforme cresce sem limites. Quebra-cabeças ou jogos com um número limitado de posições, como xadrez em um tabuleiro convencional, não podem ser completos no PSPACE, porque eles podem ser resolvidos em tempo e espaço constantes usando uma tabela de consulta muito grande . Para formular versões PSPACE completas desses jogos, eles devem ser modificados de uma forma que torne seu número de posições ilimitado, como jogá-los em um tabuleiro. Em alguns casos, como no xadrez, essas extensões são artificiais. ${\displaystyle n}$${\displaystyle n}$${\displaystyle 8\times 8}$${\displaystyle n\times n}$

Referências

Leitura adicional

• Sipser, Michael (1997), "Section 8.3: PSPACE-completeness", Introduction to the Theory of Computation , PWS Publishing, pp.  283-294 , ISBN 0-534-94728-X