¿El teorema de la jerarquía espacial se generaliza a la computación no uniforme?

Una "jerarquía espacial" no uniforme que podemos probar es una jerarquía de tamaños para programas de ramificación . Para una función booleana , deje que denote el tamaño más pequeño de un programa de ramificación que computa . Mediante un argumento análogo a este argumento de jerarquía para el tamaño del circuito , se puede mostrar que hay constantes por lo que para cada valor , hay una función tal que . $f: \{0, 1\}^n \to \{0, 1\}$ $B(f)$ $f$ $\epsilon, c$ $b \leq \epsilon \cdot 2^n / n$ $f: \{0, 1\}^n \to \{0, 1\}$ $b - cn \leq B(f) \leq b$

Creo que sería difícil separar de . Es equivalente a demostrar que algún lenguaje en tiene una complejidad de programa de ramificación súper polinomial. Un argumento simple muestra que no tiene programas de ramificación de tamaño polinómico fijo : $\mathbf{PSPACE}/\text{poly}$ $\mathbf{L}/\text{poly}$ $\mathbf{PSPACE}$ $\mathbf{PSPACE}$

Proposición. Para cada constante , hay un lenguaje modo que para todo lo suficientemente grande , . (Aquí es la función del indicador para .) $k$ $L \in \mathbf{PSPACE}$ $n$ $B(L_n) > n^k$ $L_n$ $L \cap \{0, 1\}^n$

Prueba. Según la jerarquía que probamos, hay un programa de ramificación de tamaño que calcula una función con . En el espacio polinomio, podemos iterar sobre todos los programas de ramificación de tamaño , todos los programas de ramificación de tamaño , y todas las entradas de longitud para encontrar una ramificación tal programa . Entonces podemos simular para calcular . $P$ $n^{k + 1}$ $f$ $B(f) > n^k$ $n^{k + 1}$ $n^k$ $n$ $P$ $P$ $f$

William Hoza
fuente

¿El teorema de la jerarquía espacial se generaliza a la computación no uniforme?

Respuestas: