World's most popular travel blog for travel bloggers.

Why isn't TQBF part of the polynomial hierarchy?

, , No Comments
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?

Asked By : quantumtremor
Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback