Quais são os problemas completos do pseudo-polinômio PSPACE conhecidos?

você pode fornecer uma referência ou dar exemplos particulares de problemas completos do PSPACE que são solucionáveis ​​em tempo pseudo-polinomial?

Notas adicionais:

Definição de tempo pseudo-polinomial: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

Em resposta a alguns comentários mencionados anteriormente. Perguntei anteriormente se havia algum problema PSPACE-complete que tivesse um FPTAS. A resposta surpreendente foi SIM!

Existe um determinado problema completo do PSPACE que possui um algoritmo FPTAS?

Esta é, portanto, uma pergunta de acompanhamento.

(Observe que a conjectura EXP se aplica à classe de complexidade NP, ainda existem problemas completos de NP que são solucionáveis ​​em tempo psuedo-polinomial!)

Adendo ... Sasho Nikolov perguntou sobre o FPT e o Pspace. Eu sei que existem problemas de FPT que são Pspace, Exp, Exp Space completos, etc ... Infelizmente não tenho referências ... Corrigirei quando me lembro

Obrigado!!!

Zelah

Considere Subconjunto de soma. Uma redução padrão de 3-SAT produz uma instância com valores , em que se houver um subconjunto com a soma de destino, esse conjunto conterá exatamente um de x 2 i , x 2 i + 1 para cada i . Além disso, escolher x 2 i corresponde a definir a i- variável na instância 3-SAT como true e escolher x 2 i + $x_0,\ldots,x_{2n+1}$$x_{2i},x_{2i+1}$$i$$x_{2i}$$i$$x_{2i+1}$corresponde a defini-lo como falso. É possível utilizar esta mesma redução para reduzir de quantificada 3-SAT para resultar em uma versão quantificada PSPACE-completa da soma subconjunto, , onde y i é igual à diferença entre x 2 i ou x 2 i + 1 .$\exists y_0 \forall y_1 \cdots \sum_{i}y_i = k$$y_i$$x_{2i}$$x_{2i+1}$

Você pode usar o mesmo algoritmo de tempo pseudo-polinomial para soma de subconjuntos nesta versão quantificada com algumas pequenas modificações. Nós simplesmente preencher uma tabela de todas as quantias tal que Q i y i Q i + 1 y i + 1 ⋯ Q n y n Σ n j = i y j = k (em que cada Q j é ou ∃ ou ∀ ). Esta tabela possui apenas tamanho polinomial se todos os valores estiverem delimitados polinomialmente, e não é difícil ver como preenchê-lo para $k$$Q_iy_iQ_{i+1}y_{i+1}\cdots Q_ny_n\sum_{j=i}^{n}y_j = k$$Q_j$$\exists$$\forall$ dados os valores para i - basta adicionar x 2 ( i - 1 ) e x 2 i - 1 a todos os valores para i , e tomar a união ou interseção desses conjuntos (para osquantificadores ∃ e ∀ , respectivamente).$i-1$$i$$x_{2(i-1)}$$x_{2i-1}$$i$$\exists$$\forall$

Isso não é apenas uma questão de interpretação? Vamos ser uma codificação de uma instância de QBF. Podemos interpretar w = 1 x como um número. Se w é dado em binário, esse problema é essencialmente QBF. Se conseguirmos w em unário, então temos tempo suficiente para simular a máquina PSPACE para QBF. (Talvez seja necessário preencher com um número polinomial de bits, por exemplo, w = 10 ... 01 x .)$x \in \{0,1\}^*$$w = 1x$$w$$w$$w = 10...01x$

Até funciona para EXP.

Meu exemplo favorito (devido a Grzegorczyk):

$\mathcal G_2$$x + y, x y,$$(x, y)$$x$$y$$x \dot- y$$y > x$

$\mathcal G_2$$\mathcal G_2$