Fórmulas booleanas quantificadas com alternâncias logarítmicas

Estou estudando um problema difícil para a classe de fórmulas booleanas quantificadas com um número logarítmico de alternâncias dos quantificadores. Um problema nesta classe seria semelhante a:

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

Onde $a_{\log n} = n$ , e $F$ é uma fórmula booleana das variáveis $x_1 \ldots x_n$ .

Esta classe contém claramente e está contido em uma P = P S P A C E . Existe um nome para esta classe? Existe algo mais conhecido sobre isso?$PH$$AP = PSPACE$

Com base na resposta de Michael Wehar, parece que pode facilmente mostrar que computações podem ser codificados em polysize tais QBFs: utiliza S ( log n ) alternâncias, cada um de p o l y ( n ) os bits, e fazer um argumento similar para o teorema de Savitch. Cada duas alternâncias vai dividir o tempo de execução do cálculo de um p o l y ( $NTISP(n^{\log n},poly(n))$$O(\log n)$$poly(n)$ fator.$poly(n)$

Eu chamaria a classe , seguindo a notação das " trocas de tempo no espaço para a satisfação" de Fortnow, que também poderia ser citada para o argumento esboçado no parágrafo anterior (mas consulte o documento para referências anteriores).$\Sigma_{O(\log n)} P$

(1) O que já sabemos:

Como você já declarou, o QBF com alternações de quantificadores é difícil para todos os níveis da hierarquia polinomial.$\log(n)$

(2) Penso que também podemos provar o seguinte:

O problema é -Hard.$NSPACE(log^2(n))$

(3) Aqui está minha justificativa informal para a afirmação anterior:

Dado um o espaço ligado MNT e uma cadeia de entrada, é preciso determinar se existe uma computação aceitar na dada cadeia de entrada.$log^2(n)$

Cada configuração na computação pode ser representada por essencialmente bits. Em outras palavras, podemos representar uma configuração por um grupo de variáveis de log 2 ( n ) .$\log^2(n)$$\log^2(n)$

A idéia é que tenhamos uma configuração inicial e uma configuração final e precisamos adivinhar o cálculo que ocorre no meio. Nós adivinhamos recursivamente as configurações "intermediárias" usando quantificadores existentes e recorremos verificando se a configuração "esquerda" vai para o "meio" e a configuração "média" vai para a "direita" usando todos os quantificadores.

Agora, para fazer isso funcionar, em vez de escolher uma configuração "intermediária", precisamos escolher um grupo de configurações "intermediárias" igualmente espaçadas entre as configurações "esquerda" e "direita". Em particular, poderíamos adivinhar configurações "intermediárias" igualmente espaçadas, usando quantificadores existentes com$\sqrt{n}$variáveis ​​e, em seguida, recorra a cada intervalo entre configurações, usando para todos os quantificadores com aproximadamenteasvariáveislog(n).$\sqrt{n} * log^2(n)$$\log(n)$

A recursão só precisa continuar até a profundidade para poder cobrir um cálculo do comprimento $2 * \log(n)$que cada configuração possui no máximolog2(n)muitos bits.$\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$$\log^2(n)$

Como a recursão é de profundidade , só temos O ( log ( n ) ) grupos de variáveis, ou seja, alternações. Como cada grupo de quantificadores possui apenas $O(\log(n))$$O(\log(n))$$\sqrt{n} * log^2(n)$ variables, in total we have $O(\sqrt{n} * log^3(n))$ variables.

Feel free to offer any feedback or corrections. Thank you very much and I hope this helps a little bit.

(4) A more general assertion as suggested by Ryan's answer:

You should be able to carry out the preceding construction in a more general way. Consider the following:

At each step of the recursion, break up into $g(n)$ groups of "intermediate" configurations using $c(n)$ bits per configuration. Then, do the recursion to depth $d(n)$.

As long as we don't have too many variables and too many alternations, this seems to work fine. Roughly, we need the following to be satisfied:

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

Our generalized approach will be used to simulate non-deterministic Turing machines that run for $g(n)^{d(n)}$ steps using $c(n)$ bits of memory.

In particular, we pick the following:

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

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

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

The preceding inequalities are satisfied and we can carry out the construction to simulate non-deterministic Turing machines that run for roughly $2^{\log^2(n)}$ steps using $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, we have a better hardness result than before. In particular, the problem is hard for $NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$.

(5) Further generalizations:

In the preceding generalization, we were simulating non-deterministic time and space bounded Turing machines. However, we may be able to simulate alternating time and space bounded Turing machines as well.

Let me explain a little bit. So we use roughly $\log(n)$ alternations to do the recursion to depth $\log(n)$. However, we could use some of the alternations initially, let's say $\sqrt{\log(n)}$. Then, we could use the remaining $\sqrt{\log(n)}$ alternations to go to depth $\sqrt{\log(n)}$.

In this case, we could simulate alternating Turing machines that have $\sqrt{\log(n)}$ alternations with sublinear witness lengths, run for $2^{\log^{\frac{3}{2}}(n)}$ steps, and use $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, the problem is hard for $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$ with sublinear witness lengths. Alternatively, this class could be written using the $STA$ notation mentioned in the comments above.

Thank you for the comments and feel free to offer any further corrections or clarifications. :)

A shorter answer.

Initial observations:

• The problem is hard for every level of the polynomial hierarchy.
• The problem is hard for alternating Turing machines with $\log(n)$ alternations that run for polynomial time.

Deeper Insights:

• Suggested by Kaveh's comment above, the problem can encode computations for $AltTime(\log(n), n)$ Turing machines.
• Also, as Ryan pointed out, the problem can encode computations for $NTimeSpace(2^{\log^2(n)}, \sqrt{n})$ Turing machines.

• More generally, the problem can encode computations for machines corresponding to various classes of the form $AltTimeSpace(a(n), t(n), s(n))$ with restricted witness lengths. I'm not quite sure what the exact relationship between $a(n)$, $t(n)$, and $s(n)$ has to be, but we know that:

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

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

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

See my longer answer for more details on the trade-offs between $a(n)$, $t(n)$, and $s(n)$.

Note: In the above, when I say encode computations, I mean encode the computation without blowing up the instance size too much. That is, if we blow-up from $n$ size Turing machine input to $poly(n)$ size formula, then I think that although the blow-up is polynomial, it is good to pay close attention to the degree of the polynomial. The reason for the semi-fine-grained perspective is to try and slightly better recognize how the different complexity measures $a(n)$, $t(n)$, and $s(n)$ depend on each other.