Existe um teorema da Hierarquia de Tempo para PH?

18

É 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(nk)O(nk1)

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(logn)O(loglogn)

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:

17

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.c1ΣcTIME[nk]ΠcTIME[nk1]ΣΠ

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).¸ c 1 Σ c t I M E [ n k ] Σ c t I M E [ n k - 1 ]ΣΠc1ΣcTIME[nk]ΣcTIME[nk1]

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
4
Sua pergunta mais forte será difícil de resolver afirmativamente; isso implicaria . Suponhamos que haja um c e uma língua L em Σ c t I M E [ n k ] que não está em Σ d T I H E [ n k - 1 ] para cada d . Então L O G S P A C ELOGSPACENPcLΣcTIME[nk]ΣdTIME[nk1]d . Isto é porque cada língua L G S G S P A C E é em Σ d T I H E [ n 2 ] para algumas d dependendo G (por um argumento-teorema de tipo Savitch). Portanto, se L O G S P A C E = N P , de fato, todos os idiomas em Σ c T I M E [ n kLOGSPACENPLLOGSPACEΣdTIME[n2]dLLOGSPACE=NP Está em Σ d T I M E [ n 2 ] paraalguns d , contraditório com o que você quer mostrar. ΣcTIME[nk]ΣdTIME[n2] d
Ryan Williams
3

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
1
Não, não é assim que a definição de funciona. Se Σ j t I M E [ S ( n k ) ] Σ j + 1 T I H E [ S ( N ) ] para todos os j , k , em seguida, N P C O N P . Se NΣjTIME[t(n)]ΣjTIME[O(nk)]Σj+1TIME[O(n)]j,kNPcoNP e Σ j t I M E [ S ( n k ) ] Σ j + 1 T I H E [ S ( N ) ] para todos os j , k , deixe S ( n c ) estar a correr tempo de algum algoritmo não determinístico para Tautologia. Então temos N T I M E [ O (NP=coNPΣjTIME[O(nk)]Σj+1TIME[O(n)]j,kO(nc) , 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. NTIME[O(nc2)]Σ2TIME[O(n)]NTIME[O(nc)]
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
1
A definição é a seguinte: se e somente se houver um tempo linear predicado R ( x , y 1 , ... , y i ) de tal modo que x LLΣiTIME[t(n)]R(x,y1,,yi) é verdadeiro. xL(y1:|y1|t(|x|))(yi:|yi|t(|x|))R(x,y1,,yi)
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