Existe um teorema da Hierarquia de Tempo para PH?

É verdade que existem problemas na hierarquia polinomial solucionáveis no tempo (por uma máquina de Turing alternada em algum nível da hierarquia polinomial) que não são solucionáveis em em algum nível da hierarquia polinomial? Em outras palavras - existe um teorema da hierarquia de tempo para a hierarquia polinomial como existe para P e NP? Se houver - uma referência seria ótima. $O(n^k)$ $O(n^{k-1})$

A dificuldade que encontrei é que a máquina de simulação, ao simular máquinas de todos os níveis da hierarquia, não está em nenhum nível distinto da hierarquia. O que leva a uma pergunta relacionada - a que classe menor pertence uma máquina de simulação? Existe algum sentido em definir uma classe com alternações (ou / )? $O(n)$ $O(\log n)$ $O(\log \log n)$

cc.complexity-theory reference-request polynomial-hierarchy time-hierarchy Joseph
fonte

O uso de um número linear de alternâncias fornece o PSPACE, já que a Fórmula Booleana Quantificada é completa no PSPACE.

Derrick Stolee

Respostas:

Sim. Por exemplo, as provas usuais do teorema da hierarquia de tempo (simulando diretamente máquinas arbitrárias) podem ser usadas para mostrar que para cada , não é um subconjunto de . A razão para mudar de para é que, neste argumento de diagonalização, temos que fazer o "oposto" da máquina que estamos simulando, portanto, precisamos executar no modo universal quando a máquina de simulação estiver no modo existencial , e vice versa. $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Pi_c TIME[n^{k-1}]$ $\Sigma$ $\Pi$

Você também pode obter um resultado como esse sem alternar de para : para cada , não é um subconjunto de . Isso pode ser feito usando a prova da hierarquia de tempo devido a Zak (referência: " A hierarquia de tempo de uma máquina de Turing ", Theoretical Computer Science 26 (3): 327--333, 1983). Para uma referência explícita a esta versão do teorema da hierarquia de tempo, consulte " Uma pesquisa sobre limites mais baixos de satisfação e problemas relacionados " , de Dieter van Melkebeek (disponível em sua home page). $\Sigma$ $\Pi$ $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Sigma_c TIME[n^{k-1}]$

Ryan Williams
fonte

Essa resposta demonstra muito claramente a existência de um teorema da hierarquia de tempo para todos os níveis distintos da hierarquia. Isso não indica imediatamente a presença de tal teorema para a HP como um todo.

Joseph

Sua pergunta mais forte será difícil de resolver afirmativamente; isso implicaria

. Suponhamos que haja um

e uma língua

que não está em

para cada

. Então

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

c

$c$

L

$L$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{k - 1}]

$\Sigma_d TIME[n^{k-1}]$

d

$d$

. Isto é porque cada língua

é em

para algumas

dependendo

(por um argumento-teorema de tipo Savitch). Portanto, se

, de fato, todos os idiomas em

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

L \in L O G S P A C E

$L \in LOGSPACE$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

L

$L$

L O G S P A C E = N P

$LOGSPACE = NP$

Está em

paraalguns

, contraditório com o que você quer mostrar.

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

Ryan Williams

A resposta para a pergunta revisada (revisão 4 da pergunta) é não. Se um problema de decisão L é solúvel em tempo O ( n ^k ) por um Σ _i máquina P, então L pode ser resolvido no tempo linear por uma máquina de Turing com a Oracle para G , que é um Σ _{i uma} máquina P. Portanto, TIME _i TIME [O ( n ^k )] Σ _{i +1} TEMPO [O ( n )].

Tsuyoshi Ito
fonte

Não, não é assim que a definição de

funciona. Se

para todos os

, em seguida,

. Se

Σ_{j} T I M E [t (n)]

$\Sigma_j TIME[t(n)]$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

N P \neq c o N P

$NP \neq coNP$

para todos os

, deixe

estar a correr tempo de algum algoritmo não determinístico para Tautologia. Então temos

N P = c o N P

$NP = coNP$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

O (n^{c})

$O(n^c)$

, onde o primeiro inclusão é por hipótese e o segundo inclusão seguinte a partir de um argumento de simulação padrão. Isso é uma contradição.

N T I M E [O (n^{c^{2}})] \subseteq Σ_{2} T I M E [O (n)] \subseteq N T I M E [O (n^{c})]

$NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$

Ryan Williams

@Ryan: A definição que usei é: L∈ΣiTIME [t (n)] se existir uma linguagem O∈Σ (i-1) P e uma máquina de Turing não determinística de t (n) -time com o oráculo para O que reconhece L. Pensei que essa fosse a definição padrão, mas não tenho nenhuma referência para fazer backup de minha reivindicação. Qual é a definição que você está usando?

Tsuyoshi Ito 14/02

A definição é a seguinte:

se e somente se houver um tempo linear predicado

de tal modo que

L \in Σ_{i} T I M E [t (n)]

$L \in \Sigma_i TIME[t(n)]$

R (x, y_{1}, \dots, y_{i})

$R(x,y_1,\ldots,y_i)$

é verdadeiro.

x \in L ⟺ (\exists y_{1} : | y_{1} | \leq t (| x |)) \dots (\forall y_{i} : | y_{i} | \leq t (| x |)) R (x, y_{1}, \dots, y_{i})

$x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$

Ryan Williams

@ Ryan: Ok, eu não conhecia essa definição. Se é isso que o autor da pergunta queria perguntar, minha resposta não se aplica.

Tsuyoshi Ito