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

¿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 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(n^k)$ $O(n^{k-1})$

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(n)$ $O(\log n)$ $O(\log \log n)$

cc.complexity-theory reference-request polynomial-hierarchy time-hierarchy 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:

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 , no es un subconjunto de . La razón para cambiar de a $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Pi_c TIME[n^{k-1}]$ $\Sigma$ $\Pi$ 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 , $\Sigma$ $\Pi$ $c \geq 1$ no es un subconjunto de . 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 $\Sigma_c TIME[n^k]$ $\Sigma_c TIME[n^{k-1}]$ " 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

Su pregunta más fuerte será difícil de resolver afirmativamente; que implicaría

. Suponga que hay una

y un lenguaje

que no está en

para cada

. Entonces

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$

. Esto se debe a que cada lenguaje

está en

para algunos

dependiendo de

(mediante un argumento de tipo teorema de Savitch). Entonces, si

entonces, de hecho, todos los idiomas en

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á en

poralgún

, contradictorio con lo que quieres 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

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

No, no es así como funciona la definición de

. Si

para todo

, entonces

. Si

Σ_{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$

N P = c o N P

$NP = coNP$

por cada

, que

sea la carrera tiempo de algún algoritmo no determinista para Tautología. Entonces tenemos

Σ_{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)$

, 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.

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: 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

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

$L \in \Sigma_i TIME[t(n)]$ si hay un predicado de tiempo lineal

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

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

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)$ 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