Quantified Boolean Formulas with logarithmic alternations 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?
(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.  :)