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

11

Pregunta general

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

Aquí hay algunas preguntas más específicas:

  • ¿Es ?L/polyPSPACE/poly

  • Para todas las funciones construibles en el espacio f(n) , ¿es DSPACE(o(f(n)))/polyDSPACE(f(n))/poly ?

  • Para qué funciones h(n) se sabe que: para todo el espacio construible f(n) , DSPACE(o(f(n)))/h(n)DSPACE(f(n))/h(n) ?

Michael Wehar
fuente

Respuestas:

7

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{0,1}B(f)fϵ,cbϵ2n/nf:{0,1}n{0,1}bcnB(f)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 :PSPACE/polyL/polyPSPACEPSPACE

Proposición. Para cada constante , hay un lenguaje modo que para todo lo suficientemente grande , . (Aquí es la función del indicador para .)kLPSPACEnB(Ln)>nkLnL{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 .Pnk+1fB(f)>nknk+1nknPPf

William Hoza
fuente