Fórmulas booleanas cuantificadas con alternancias logarítmicas

Estoy estudiando un problema que es difícil para la clase de fórmulas booleanas cuantificadas con un número logarítmico de alternancias de los cuantificadores. Un problema en esta clase se vería así:

$\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F$

Donde , y es una fórmula booleana de las variables .$a_{\log n} = n$$F$$x_1 \ldots x_n$

Esta clase contiene claramente y está contenida en AP = PSPACE . ¿Hay un nombre para esta clase? ¿Hay algo más conocido al respecto?$PH$$AP = PSPACE$

Sobre la base de la respuesta de Michael Wehar, parece que puede mostrar fácilmente que los cálculos de se pueden codificar en polisize tales QBF: utiliza alternancias O ( log n ) , cada uno de p o l y ( n ) bits, y hacer un argumento similar al teorema de Savitch. Cada dos alternancias dividirá el tiempo de funcionamiento de la computación por un p o l y ( $NTISP(n^{\log n},poly(n))$$O(\log n)$$poly(n)$ factor.$poly(n)$

Llamaría a la clase , siguiendo la anotación en "Intercambios tiempo-espacio para la satisfacción" de Fortnow que también podría citarse para el argumento esbozado en el párrafo anterior (pero consulte el documento para referencias anteriores).$\Sigma_{O(\log n)} P$

(1) Lo que ya sabemos:

Como ya ha dicho, QBF con alternancia de cuantificadores es difícil para todos los niveles de la jerarquía polinómica.$\log(n)$

(2) Creo que también podemos probar lo siguiente:

El problema es -hard.$NSPACE(log^2(n))$

(3) Aquí está mi justificación informal para la afirmación anterior:

Dado un espacio NTM y una cadena de entrada, necesitamos determinar si existe un cálculo de aceptación en la cadena de entrada dada.$log^2(n)$

Cada configuración en el cálculo se puede representar esencialmente mediante bits. En otras palabras, podemos representar una configuración mediante un grupo de variables log 2 ( n ) .$\log^2(n)$$\log^2(n)$

La idea es que tenemos una configuración inicial y una configuración final y necesitamos adivinar el cálculo que ocurre en el medio. Adivinamos recursivamente las configuraciones "medias" usando cuantificadores existentes y verificamos recurrentemente que la configuración "izquierda" va al "medio" y la configuración "media" va a la "derecha" usando para todos los cuantificadores.

Ahora, para que esto funcione, en lugar de elegir una configuración "intermedia", necesitamos elegir un grupo de configuraciones "intermedias" igualmente espaciadas entre las configuraciones "izquierda" y "derecha". En particular, podríamos adivinar configuraciones "intermedias" igualmente espaciadas usando cuantificadores existentes con$\sqrt{n}$variables y luego recurren en cada espacio entre configuraciones utilizando para todos los cuantificadores con aproximadamente lasvariableslog(n).$\sqrt{n} * log^2(n)$$\log(n)$

La recursión solo necesita continuar hasta la profundidad para poder cubrir un cálculo de longitud $2 * \log(n)$donde cada configuración tiene como máximolog2(n)muchos bits.$\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$$\log^2(n)$

Como la recursividad es de profundidad , solo tenemos grupos de variables O ( log ( n ) ) , es decir, alternancias. Dado que cada grupo de cuantificadores solo tiene $O(\log(n))$$O(\log(n))$variables, en total tenemosO($\sqrt{n} * log^2(n)$variables.$O(\sqrt{n} * log^3(n))$

Siéntase libre de ofrecer cualquier comentario o corrección. Muchas gracias y espero que esto ayude un poco.

(4) Una afirmación más general como lo sugiere la respuesta de Ryan:

Debería poder llevar a cabo la construcción anterior de una manera más general. Considera lo siguiente:

En cada paso de la recursión, divídase en grupos de configuraciones "intermedias" utilizando c ( n ) bits por configuración. Luego, haz la recursión a la profundidad d ( n ) .$g(n)$$c(n)$$d(n)$

Mientras no tengamos demasiadas variables y demasiadas alternancias, esto parece funcionar bien. Aproximadamente, necesitamos lo siguiente para estar satisfecho:

• $g(n) * c(n) * d(n) \leq n$
• $d(n) \leq \log(n)$

Nuestro enfoque generalizado se utilizará para simular máquinas Turing no deterministas que se ejecutan por pasos utilizando bits de memoria c ( n ) .$g(n)^{d(n)}$$c(n)$

En particular, elegimos lo siguiente:

• $g(n) = \sqrt{n}$

• $c(n) = \frac{\sqrt{n}}{2 * log^2{n}}$

• $d(n) = 2 * \log^2(n)$

Las desigualdades anteriores se satisfacen y podemos llevar a cabo la construcción para simular máquinas de Turing no deterministas que se ejecutan durante aproximadamente pasos log 2 ( n ) utilizando $2^{\log^2(n)}$ bits de memoria.$\frac{\sqrt{n}}{2 * log^2{n}}$

En otras palabras, tenemos un mejor resultado de dureza que antes. En particular, el problema es difícil para .$NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$

(5) Otras generalizaciones:

En la generalización anterior, estábamos simulando máquinas Turing no deterministas de tiempo y espacio. Sin embargo, también podremos simular máquinas de Turing con límites de tiempo y espacio alternos.

Déjame explicarte un poco. Por lo tanto, utilizamos aproximadamente las alternancias para hacer la recursividad al registro de profundidad ( n ) . Sin embargo, podríamos usar algunas de las alternancias inicialmente, digamos $\log(n)$$\log(n)$ . Entonces, podríamos usar el √ restante$\sqrt{\log(n)}$ alternancias para ir a profundidad$\sqrt{\log(n)}$ .$\sqrt{\log(n)}$

En este caso, podríamos simular máquinas Turing alternativas que tengan alternancias con longitudes de testigos sublineales, ejecute para2 log $\sqrt{\log(n)}$pasos, y use$2^{\log^{\frac{3}{2}}(n)}$ bits de memoria.$\frac{\sqrt{n}}{2 * log^2{n}}$

En otras palabras, el problema es difícil para con longitudes de testigos sublineales. Alternativamente, esta clase podría escribirse usando lanotaciónSTAmencionada en los comentarios anteriores.$AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$$STA$

Gracias por los comentarios y no dude en ofrecer más correcciones o aclaraciones. :)

Una respuesta más corta.

Observaciones iniciales:

• El problema es difícil para todos los niveles de la jerarquía polinómica.
• El problema es difícil para alternar máquinas de Turing con alternancias que se ejecutan por tiempo polinómico.$\log(n)$

Perspectivas más profundas:

• Sugerido por el comentario de Kaveh anterior, el problema puede codificar cálculos para máquinas Turing.$AltTime(\log(n), n)$
• Además, como señaló Ryan, el problema puede codificar cálculos para Máquinas de Turing.$NTimeSpace(2^{\log^2(n)}, \sqrt{n})$

• De manera más general, el problema puede codificar cálculos para máquinas correspondientes a varias clases de la forma con longitudes de testigo restringidas. No estoy muy seguro de cuál es la relación exacta entre a ( n ) , t ( n ) y s ( n $AltTimeSpace(a(n), t(n), s(n))$$a(n)$$t(n)$$s(n)$ tiene que ser, pero sabemos que:

  1. $\; \; a(n) \leq \log(n)$

  2. $\; \; t(n) \leq 2^{\log^2(n)}$

  3. $\; \; s(n) \leq n$

$a(n)$$t(n)$$s(n)$

$n$$poly(n)$$a(n)$$t(n)$$s(n)$