Problemas com o EXPSPACE

Atualmente, estou tentando encontrar problemas completos do EXPSPACE (principalmente para encontrar inspiração para uma redução) e estou surpreso com o pequeno número de resultados que estão chegando.

Até agora, eu os encontrei e tenho problemas para expandir a lista:

• universalidade (ou outras propriedades) de expressões regulares com exponenciação.
• problemas relacionados aos sistemas de adição de vetores
• jogos não observáveis ​​(veja, por exemplo, este blog )
• algum fragmento de FO-LTL, em Sobre a complexidade computacional de fragmentos decidíveis de lógicas temporais lineares de primeira ordem

Você conhece outros contextos em que a completude EXPSPACE aparece naturalmente?

Estendendo o exemplo apontado por Emil Jerabek nos comentários, os problemas surgem naturalmente em toda a geometria algébrica. Isso começou (eu acho) com o Problema de Associação Ideal ( Mayr – Meyer e Mayr ) e, portanto, o cálculo das bases de Gröbner. Isto foi então estendido ao cálculo de syzygies ( Bayer e Stillman ). Muitos problemas naturais da geometria algébrica computacional acabam sendo equivalentes a um desses problemas. Veja também a pesquisa da Bayer – Mumford "O que pode ser calculado em geometria algébrica?"$\mathsf{EXPSPACE}$

Muitos problemas que são completos no PSPACE se tornam completos no EXPSPACE quando a entrada é fornecida "de forma sucinta", ou seja, por meio de alguma codificação que permite descrever entradas que normalmente seriam de tamanho exponencial.

Aqui está um exemplo de autômatos finitos (equivalentemente, em gráficos direcionados com bordas rotuladas): decidir se dois autômatos aceitam o mesmo idioma (têm o mesmo conjunto de caminhos rotulados de uma origem para um nó de destino) é completo no PSPACE. Se os autômatos (gráficos) são fornecidos por fórmulas booleanas (nós são avaliações v, v ', .. e existem fórmulas booleanas informando se va> v' é uma aresta), o problema se torna EXPSPACE completo. Nota: existem muitas outras maneiras de definir sucintamente um gráfico / autômato grande, veja, por exemplo, este artigo .

O exemplo com expressões regulares se encaixa nesse padrão. A introdução de uma notação ".. ^ 2" para quadratura permite que você escreva expressões regulares compactas que seriam muito grandes se você expandisse cada "(foo) ^ 2" por "foo foo" e "((bar) ^ 2) ^ 2 "por" bar bar bar bar ". Naturalmente, alguns problemas que são completos no PSPACE sem quadrado se tornam EXPSPACE completos com o quadrado permitido, eis a referência clássica . [NB: Outros exemplos, como expressões regulares com interseção ou complementos, obviamente não se encaixam no padrão de nova notação que se expande em entradas exponencialmente maiores na notação padrão.]

Da mesma forma, um problema completo com LOGSPACE (por exemplo, alcançabilidade em gráficos direcionados) pode se tornar completo com EXPSPACE se sua codificação sucinta permitir a descrição de gráficos com tamanho duplamente exponencial.

Conclusão: você pode facilmente encontrar problemas novos, embora talvez artificiais, completos com o EXPSPACE, considerando problemas clássicos do PSPACE ou LOGSPACE (dos quais você encontrará muitos) e permitindo a codificação compacta / sucinta / .. da entrada.

O planejamento temporal com ações simultâneas é EXPSPACE-complete, conforme mostrado em

J. Rintanen, “Complexidade do planejamento temporal simultâneo”, Anais da 17ª Conferência Internacional sobre Planejamento e Programação Automatizados, pp. 280–287, 2007

O problema é aproximadamente o seguinte (cuidado no artigo acima, ele é definido de uma maneira diferente, mas equivalente). Seja um conjunto finito de variáveis ​​proposicionais e um conjunto finito de ações , onde cada ação é , onde:O o = ( d , P s , P e , P o , E s , E e$A$$O$$o=(d,P_s,P_e,P_o,E_s,E_e)$

• $d\in\mathbb{N}$ é a duração da ação.
• P e P o$P_s$ , e são as pré-condições da ação , que são fórmulas proposicionais sobre que devem ser verdadeiras, respectivamente, no início, no final e durante toda a execução da ação para que seja aplicável.$P_e$$P_o$$A$
• E e$E_s$ e são conjuntos de literais sobre que especificam os efeitos inicial e final ( isto é , como a ação afeta as variáveis ​​de estado).$E_e$$A$

O problema é que, dada uma avaliação das variáveis ​​de estado que descrevem o estado inicial, e uma fórmula proposicional que descreve a condição do objetivo , descobrir se existe uma maneira de organizar as ações, possivelmente sobrepostas no tempo, de modo que, se aplicadas de , conduzo a um estado em que mantém.G I $I$$G$$I$$G$

Observe que, seguindo a prova, pode-se argumentar que a completude EXPSPACE vem novamente da sucessão da entrada numérica (mas não apenas isso, de qualquer maneira), mas uma entrada unária seria muito antinatural, por isso acho que esse é um problema que é naturalmente EXPSPACE-complete.$d$

A maioria das classes padrão do PSPACE on (bem, mesmo para NP, se você preferir) tem algum problema de ladrilho como um problema completo. Tais problemas de lado a lado não estão muito longe dos problemas completos da máquina de Turing natural, mas geralmente são bastante convenientes como ponto de partida para reduções. Em poucas palavras, um problema de ladrilhos fornece um conjunto de ladrilhos permitidos (ou seja: tipos de ladrilhos dos quais você pode usar quantos ladrilhos você quiser) e decide como eles podem ser combinados, geralmente por um conjunto H de pares de telhas e um conjunto V de tipos permitidos verticalmente. Além disso, um primeiro bloco e um último bloco podem ser fornecidos e, dependendo da versão real, e quantas linhas e / ou colunas o bloco deve ter. A questão algorítmica é se existe um ladrilho correto, ou seja, uma atribuição de posições aos ladrilhos, que obedeça a todas as restrições e tenha o bloco inicial na posição inferior esquerda e o último bloco na posição superior direita. (Existem muitas variações quanto às definições exatas).

Para a classe disponível, EXPSPACE, você pode escolher entre (pelo menos) duas versões:

• lado a lado exponencial do corredor de largura, onde um parâmetro n é fornecido e a questão é se existe um lado a lado com 2 ^ n colunas e qualquer número de linhas
• Jogo de ladrilhos exp-times-exp, onde, dado n, o ladrilho deve ser do tamanho 2 ^ n vezes 2 ^ n, onde o primeiro jogador tem como objetivo alcançar um ladrilho correto e o segundo jogador tenta impedir isso.

Os documentos a serem analisados ​​são: Bogdan S. Chlebus: "Jogos de Dominó-Azulejo". J. Comput. Syst. Sci. 32 (3): 374-392 (1986) - Peter van Emde Boas: "A conveniência das inclinações", em: Complexidade, lógica e teoria da recursão, notas de aula em matemática pura e aplicada, vol. 187, 1997, pp. 331-363.

Um exemplo e prova são dados em Introdução à teoria dos autômatos, linguagens e computação Hopcroft / Ullman Thm13.16, de que qualquer algoritmo não determinístico para a teoria de reais de primeira ordem com adição é NExpTime. portanto, é presumivelmente também difícil para o NExpSpace, a menos que algum avanço teórico prove que ele pode ser resolvido "em um espaço mais apertado", mas é claro que essa pergunta é semelhante (quase idêntica?) a L =? P. (em outras palavras, todos os problemas conhecidos no NExpTime também são candidatos básicos ao NExpSpace, e se houver algum provável, provavelmente significaria uma solução inovadora para uma separação de classes de complexidade aberta há muito tempo.) a prova vem de Fischer, Rabin 1974, "Complexidade superexponencial da aritmética de Presburger", Complexidade da computação(R. Karp ed.). Anais do Simpósio SIAM-AMS em Matemática Aplicada.