Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Many computational complexity researchers believe that finite-level collapse of polynomial hierarchy is unlikely. Why do they believe like this?

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

It's possible to generalize to this conclusion essentially directly from the opinion that P $\neq$ NP. Let's think of NP-completeness via SAT, the problem of satisfying a Boolean formula in $n$ variables. In the polynomial hierarchy PH, we construct complete problems similarly by allowing quantifier alternations e.g. $\forall X_1 \exists X_2 ... \forall X_n \varphi(X_1,...,X_n)$. Here the $X_i$ might be sets of variables, not just individuals, in the Boolean formula $\varphi$. The problem of satisfying the kind of formula given is $\Pi_n^P$ complete, while if I'd started with $\exists$ it would have been $\Sigma_n^P$ complete.

OK, now suppose PH collapses, so that say for all $n > n_0: \Pi^P_n, \Sigma^P_n \subset \Sigma^P_{n_0}$. Then TQBF$_{n_0},$ the complete problem described above for $\Sigma^P_{n_0}$, is actually complete for PH as a whole. Conversely, if PH has any complete problem, it must lie at some finite level, in which all higher levels must then be contained, so we see PH collapses if and only if it has a complete problem. This bothers people in the same way as the idea that NP $\subset$ P. In the latter case, we'd have to be able in general to find a needle in a haystack without having to look at each piece of hay, while decades of work seem to indicate that NP problems can't generally be approached any more efficiently than via brute force. For higher polynomial complexity classes, the parallel supposition is that we can't find out, for example, whether a $\Sigma^P_2$ formula $\exists X_1 \forall X_2 \varphi(X_1,X_2)$ is satisfiable any more efficiently than by iterating through all possible assignments to the variables $X_1$ and, on each step of that loop, checking whether we can satisfy $\varphi$ with each possible assignment to the $X_2$.

So, if you're skeptical about the assumption that P $\neq$ NP, that's stronger than being skeptical that PH collapses to any particular finite level, but in essence this holds conversely, too: if I can drop off all but $k$ alternations of quantifiers on PH problems, I am going to have to take much more seriously the idea that I can drop off all the quantifiers-namely the idea that P = NP.

The last issue worth mentioning regards PSPACE. The quantified Boolean formula problem TQBF with arbitrarily many quantifier alternations is PSPACE complete, which shows that at least PSPACE $\supset$ PH. If PH=PSPACE, then PH collapses, because then TQBF sits at some finite level of the hierarchy and is PH-complete. On the other hand, if PH collapses, it might suggest PH=PSPACE, because otherwise we'd be in the very strange situation where each fixed TQBF$_n$ was reducible to TQBF$_{n_0}$ for some $n_0$ while the unbounded TQBF was not.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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