15
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Well, it's complete for alternating polynomial time with logarithmically many alternations. $\endgroup$ – Emil Jeřábek Feb 24 '17 at 9:07
  • 2
    $\begingroup$ An agreed notation for the complexity class of this problem would be STA($\ast,n^{O(1)}, O(\log n)$). Here, STA(s(n), t(n), a(n)) is the space-time-alternation measure introduced by Berman in "The complexity of logical theories" which appeared in TCS in 1980. This class contains all decision problem decidable by an alternating Turing machine in time t(n) using space s(n) and alternating at most a(n) times on every computation branch. As Emil pointed out, your problem should be complete for this class. $\endgroup$ – Christoph Haase Feb 24 '17 at 12:18
  • 2
    $\begingroup$ AltTime(lg n, poly(n)) $\endgroup$ – Kaveh Feb 25 '17 at 3:06
  • $\begingroup$ Isn't it also the binary analog of the class FOLL introduced by Barrington, Kadau, McKenzie and Lange. FOLL is defined by iterating an FO block basically an n-input, n-output uniform AC0 circuit loglog n times. It is too weak to compute Parity but is not known to be contained in a class smaller than AC^1. It can do a number of nontrivial stuff including powering in a commutative group presented as a multiplication table. I would like to call the class in question PHL because it corresponds to a PH block iterated log n times. I think it is still not clear if it is comparable to PSPACE. $\endgroup$ – SamiD Feb 27 '17 at 15:24
  • $\begingroup$ Also if an abelian group is given by a circuit which takes input two n-bit numbers and outputs an n-bit number then powering is in PHL by a proof similar to Barrington et al above. $\endgroup$ – SamiD Feb 27 '17 at 15:28
7
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for the comment and follow-up answer. I edited my answer and added details on generalizing the argument. There is actually a time, space, and alternation trade-off for the kinds of computations that can be encoded. $\endgroup$ – Michael Wehar Feb 25 '17 at 5:35
  • $\begingroup$ Thank you for the added reference! Also, I added a more succinct answer to hopefully clarify. Thanks again. :) $\endgroup$ – Michael Wehar Feb 25 '17 at 7:39
7
$\begingroup$

(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. :)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Wouldn't the $NL^2$-hardness follow straightaway from PH-hardness? $\endgroup$ – Nikhil Feb 24 '17 at 11:41
  • 1
    $\begingroup$ How exactly do we know point (1)? Don't we need $2^k$ variables to get to some level $k$ of PH? Maybe I'm missing a simple point here. $\endgroup$ – Markus Feb 24 '17 at 20:03
  • 1
    $\begingroup$ @MichaelWehar Sure, but we do know that $NL^2 \subseteq PH$ right? And that means every problem in $NL^2$ reduces to QBF with constantly many alternations, which is a special case of log-many alternations? $\endgroup$ – Nikhil Feb 24 '17 at 21:01
  • 1
    $\begingroup$ @MichaelWehar Oops. Of course you're right! A related question here: cstheory.stackexchange.com/questions/14159/… $\endgroup$ – Nikhil Feb 24 '17 at 21:17
  • 2
    $\begingroup$ Why not $NTISP(n^{\log n},poly(n))$-hard? $\endgroup$ – Ryan Williams Feb 24 '17 at 23:22
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Also, there is another factor that I omitted. That is, the witness size used with each alternation takes up variables. In other words, the larger the witnesses, the fewer variables that we have meaning that potentially we can't represent as many bits per configuration causing us to possibly require there to be less space for the machine that we encode computations for. $\endgroup$ – Michael Wehar Feb 25 '17 at 6:33
  • $\begingroup$ Basically, all witness lengths for the quantifiers are sublinear and how large we can make them depends on the choice of $a(n)$, $t(n)$, and $s(n)$. $\endgroup$ – Michael Wehar Feb 25 '17 at 10:12
  • $\begingroup$ Maybe an inner most there exists quantifier doesn't need to have restricted witness size because we can guess as we go. $\endgroup$ – Michael Wehar Feb 25 '17 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.