¿Existe un teorema de jerarquía de tiempo para PH?

18

¿Es cierto que hay problemas en la jerarquía polinómica que se pueden resolver en el tiempo (por una máquina de Turing alterna en algún nivel de la jerarquía polinómica) que no se pueden resolver en O ( n k - 1 ) en ningún nivel de jerarquía polinómica? En otras palabras, ¿existe un teorema de jerarquía de tiempo para la jerarquía polinómica como existe para P y NP? Si es así, una referencia sería genial.O(nk)O(nk1)

La dificultad que encontré es que la máquina de simulación, cuando simula máquinas de todos los niveles de la jerarquía, no está en ningún nivel distinto de la jerarquía. Lo que lleva a una pregunta relacionada: ¿cuál es la clase más pequeña a la que pertenece una máquina de simulación? ¿Tiene algún sentido definir una clase con alternancias (u O ( log n ) / O ( log log n ) )?O(n)O(logn)O(loglogn)

José
fuente
El uso de un número lineal de alternancias le proporciona PSPACE, ya que la fórmula booleana cuantificada es completa para PSPACE.
Derrick Stolee

Respuestas:

17

Si. Por ejemplo, las pruebas habituales del teorema de la jerarquía temporal (simulando directamente máquinas arbitrarias) se pueden usar para mostrar que por cada , Σ c T I M E [ n k ] no es un subconjunto de Π c T I M E [ n k - 1 ] . La razón para cambiar de Σ a Πc1ΣcTIME[nk]ΠcTIME[nk1]ΣΠ es que, en este argumento de diagonalización, tenemos que hacer el "opuesto" de la máquina que estamos simulando, por lo que debemos ejecutar en modo universal cuando la máquina de simulación está en modo existencial, y viceversa.

También puede obtener un resultado como este sin cambiar de a Π : por cada c 1 , ΣΣΠc1 no es un subconjunto de Σ c T I M E [ n k - 1 ] . Esto se puede hacer usando la prueba de la jerarquía de tiempo debido a Zak (referencia: "Una jerarquía de tiempo de máquina de Turing", Theoretical Computer Science 26 (3): 327--333, 1983). Para una referencia explícita a esta versión del teorema de la jerarquía del tiempo, verDieter van MelkebeekΣcTIME[nk]ΣcTIME[nk1]" Una encuesta de límites más bajos para la satisfacción y los problemas relacionados " (disponible en su página de inicio).

Ryan Williams
fuente
Esta respuesta demuestra muy claramente la existencia de un teorema de jerarquía de tiempo para cada nivel distinto de la jerarquía. Esto no indica inmediatamente la presencia de dicho teorema para el PH en su conjunto.
Joseph
44
Su pregunta más fuerte será difícil de resolver afirmativamente; que implicaría . Suponga que hay una c y un lenguaje L en Σ c T I M E [ n k ] que no está en Σ d T I M E [ n k - 1 ] para cada d . Entonces L O G S P A C ELOGSPACENPcLΣcTIME[nk]ΣdTIME[nk1]d . Esto se debe a que cada lenguaje L L O G S P A C E está en Σ d T I M E [ n 2 ] para algunos d dependiendo de L (mediante un argumento de tipo teorema de Savitch). Entonces, si L O G S P A C E = N P, entonces, de hecho, todos los idiomas en Σ c T I M E [ n kLOGSPACENPLLOGSPACEΣdTIME[n2]dLLOGSPACE=NP está en Σ d T I M E [ n 2 ] poralgún d , contradictorio con lo que quieres mostrar. ΣcTIME[nk]ΣdTIME[n2] d
Ryan Williams
3

La respuesta a la pregunta revisada (revisión 4 de la pregunta) es no. Si un problema de decisión L es solucionable en el tiempo O ( n k ) por una máquina ∑ i P, entonces L puede resolverse en tiempo lineal por una máquina Turing con el oráculo para L , que es una máquina ∑ i +1 P. Por lo tanto, ∑ i TIEMPO [O ( n k )] ⊆ Σ i +1 TIEMPO [O ( n )].

Tsuyoshi Ito
fuente
1
No, no es así como funciona la definición de . Si Σ j T I M E [ O ( n k ) ] Σ j + 1 T I M E [ O ( n ) ] para todo j , k , entonces N P c o N P . Si NΣjTIME[t(n)]ΣjTIME[O(nk)]Σj+1TIME[O(n)]j,kNPcoNP y Σ jNP=coNP por cada j , k , que O ( n c ) sea ​​la carrera tiempo de algún algoritmo no determinista para Tautología. Entonces tenemos N T I M E [ O (ΣjTIME[O(nk)]Σj+1TIME[O(n)]j,kO(nc) , donde la primera inclusión es por suposición y la segunda inclusión se deriva de un argumento de simulación estándar. Esto es una contradicción. NTIME[O(nc2)]Σ2TIME[O(n)]NTIME[O(nc)]
Ryan Williams
@Ryan: La definición que utilicé es: L∈ΣiTIME [t (n)] si existe un lenguaje O∈Σ (i − 1) P y una máquina Turing de tiempo no determinista t (n) con el oráculo para O que reconoce L. Pensé que esta es la definición estándar, pero no tengo ninguna referencia para respaldar mi reclamo. ¿Cuál es la definición que estás usando?
Tsuyoshi Ito
1
LΣyoTyoMETROmi[t(norte)] si hay un predicado de tiempo lineal R(x,y1,,yi) such that xL(y1:|y1|t(|x|))(yi:|yi|t(|x|))R(x,y1,,yi) is true.
Ryan Williams
@Ryan: Ok, I did not know that definition. If that is what the asker wanted to ask, my answer does not apply.
Tsuyoshi Ito