Quantified Boolean Formulas with logarithmic alternations

Question

I'm studying a problem which is hard for the class of quantified boolean formulas with a logarithmic number of alternations of the quantifiers. A problem in this class would look like:

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

Where $a_{\log n} = n$, and $F$ is a boolean formula of the variables $x_1 \ldots x_n$.

This class clearly contains $PH$ and is contained in $AP = PSPACE$. Is there a name for this class? Is there anything more known about it?

Answer 1

Building on Michael Wehar's answer, it seems that you can easily show that $NTISP(n^{\log n},poly(n))$ computations can be encoded in polysize such QBFs: you use $O(\log n) $ alternations, each of $poly(n)$ bits, and do an argument similar to Savitch's theorem. Every two alternations will divide the running time of the computation by a $poly(n)$ factor.

I would call the class $\Sigma_{O(\log n)} P$, following the notation in Fortnow's "Time-Space Tradeoffs for Satisfiability" which could also be cited for the argument sketched in the previous paragraph (but please see the paper for earlier references).

Answer 2

(1) What we already know:

As you've already stated, QBF with $\log(n)$ alternations of quantifiers is hard for every level of the polynomial hierarchy.

(2) I think that we can also prove the following:

The problem is $NSPACE(log^2(n))$-hard.

(3) Here is my informal justification for the preceding assertion:

Given a $log^2(n)$ space bound NTM and an input string, we need to determine whether there exists an accepting computation on the given input string.

Each configuration in the computation can be represented by essentially $\log^2(n)$ bits. In other words, we can represent a configuration by a group of $\log^2(n)$ variables.

The idea is that we have a start configuration and a final configuration and we need to guess the computation that happens in between. We recursively guess the "middle" configurations using exist quantifiers and recurse verifying that the "left" configuration goes to the "middle" and the "middle" configuration goes to the "right" using for all quantifiers.

Now to make this work, instead of picking one "middle" configuration, we need to pick a group of equally spaced "intermediate" configurations between the "left" and "right" configurations. In particular, we could guess $\sqrt{n}$ equally spaced "intermediate" configurations using exist quantifiers with $\sqrt{n} * log^2(n)$ variables and then recurse on every gap between configurations using for all quantifiers with roughly $\log(n)$ variables.

The recursion only needs to continue on to depth $2 * \log(n)$ to be able to cover a computation of length $\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$ where each configuration has at most $\log^2(n)$ many bits.

Since the recursion is of depth $O(\log(n))$, we only have $O(\log(n))$ groups of variables i.e. alternations. Since each group of quantifiers only has $\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. :)

Answer 3

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.