2
$\begingroup$

TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$. So given a formula in TQBF, shouldn't there be a level of the polynomial hierarchy that solves it?

I think this is incorrect because TQBF consists of any number of quantifiers, but each level in the PH has fixed number of quantifiers, so there's no level of the PH that can solve TQBF. Does it have to do with the fact that the number of quantifiers is part of the input in TQBF, whereas in PH only the formula is the input?

So this could also be worded as, if there exists a PH-complete problem, does TQBF reduce to that problem?

$\endgroup$
2
$\begingroup$

What you're missing is the distinction between QBF and 2QBF.

It's an open problem whether TQBF is contained in any level of the polynomial hierarchy, but it'd be reasonable to expect that TQBF is probably not contained in any level of the polynomial hierarchy.

TQBF is PSPACE-complete. Also, if PSPACE = PH, then the polynomial hierarchy collapses. Thus, if TQBF is in some level of the polynomial hierarchy, then so is all of PSPACE, and thus the polynomial hiearchy collapses.

It is conjectured that the polynomial hierachy does not collapse. However, this is merely a conjecture, analogous to the conjecture that P $\ne$ NP; whether or not this is true is an open problem.

TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$.

Giraffes consist of atoms. So do light bulbs. Therefore, every giraffe is also a light bulb.

What's wrong with that reasoning? The same thing that's wrong with your reasoning.

Check your definitions. $\Sigma_n^2$ allows formulas that contain only two alternations of quantifiers, i.e., 2QBF. QBF allows an unlimited number of alternations of quantifiers. 2QBF is complete for $\Sigma_n^2$; QBF is complete for PSPACE.

$\endgroup$
  • $\begingroup$ But for any given problem in TQBF, it has a finite number of quantifiers right? So if we had a PH-complete oracle, we could use it to solve any TQBF problem. $\endgroup$ – quantumtremor Sep 1 '16 at 23:01
  • 1
    $\begingroup$ @quantumtremor, No, that's not right. You're overlooking the distinction between a problem (language) and an instance. Any one QBF formula has a finite number of quantifiers, but TQBF is the class of all such true formula, without limit on the number of quantifiers (there's no upper bound on it). Consider $\mathbb{Z}$; every integer is finite, but $\mathbb{Z}$ is not a finite set. Or, consider 3-colorability, a NP-complete problem. Every instance of 3-colorability is finite, but this doesn't imply it can be solved in $O(1)$-time, and 3-colorability is not a finite language. $\endgroup$ – D.W. Sep 1 '16 at 23:04
  • $\begingroup$ @quantumtremor, let me explain in a different way. If there exists any PH-complete problem, then the polynomial hierarchy collapses. So you can't just assume that some PH-complete problem (or oracle) exists. $\endgroup$ – D.W. Sep 1 '16 at 23:22

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.