World's most popular travel blog for travel bloggers.

# Why isn't TQBF part of the polynomial hierarchy?

, ,
Problem Detail:

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?

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.

Question Source : http://cs.stackexchange.com/questions/63074

3200 people like this