12
$\begingroup$

The Baker-Gill-Solovay result showed that the P = NP question does not relativize, in the sense that no relativizing proof (insensitive to the presence of an oracle) can possibly settle the P = NP question.

My question is: Is there a similar result for the question, "Does there exist a PH-complete problem?" An answer in the negative to this question would imply P != NP; an answer in the affirmative would be unlikely but interesting because it would mean that PH collapses to some level.

I'm not sure, but I suspect that a TQBF oracle would lead PH to be equal to PSPACE, and thus to have a complete problem. In addition to being uncertain regarding this, I am curious as to whether or not there is an oracle relative to which PH provably does not have a complete problem.

-Philip

$\endgroup$
16
$\begingroup$

Yao showed, in 1985, that there exist oracles relative to which the Polynomial Hierarchy is infinite. Relative to such an oracle, there don't exist PH-complete problems.

Also, you are right that with a TQBF oracle, PH equals PSPACE. In fact, even P = PSPACE in the presence of a TQBF oracle.

$\endgroup$
  • $\begingroup$ Thanks, this was the first answer the precisely answered my question. $\endgroup$ – Philip White Nov 18 '10 at 2:35
  • $\begingroup$ Just to make one point clear to readers, there are $\Sigma_k P^A$-complete problems for every oracle $A$. That is, there are always complete problems for every fixed level of the hierarchy. Namely, deciding if player 1 wins a given $k$-round game, where the game's referee is described by a circuit with oracle access to $A$, is $\Sigma_k P$-complete. (I'm assuming here that player 1 gets the first move; otherwise it's $\Pi_k P$-complete.) $\endgroup$ – Andy Drucker Dec 26 '12 at 17:23
14
$\begingroup$

PH has complete problems if and only if it collapses: if it has a complete problem $L$, then $L \in \Sigma_k P$ for some $k$, so $PH = \Sigma_k P$. Conversely, if $PH$ is finite, then $PH = \Sigma_k P$ for some $k$, and $\Sigma_k SAT$ is then PH-complete.

As pointed out by Srikanth, there are oracles relative to which PH is infinite. (In fact, finding such oracles was part of the reason people started looking at PARITY not in $AC^0$ in the first place.) Using similar circuit-based techniques, there is also, for every $k$, an oracle that collapses $PH$ to exactly $\Sigma_k P$ (Ker-I Ko, SICOMP 18(2), 1989). For those who are interested, I recommend Ker-I Ko's survey.

$\endgroup$
  • $\begingroup$ Thank you, this answer is also useful. I think I knew that it has complete problems iff it collapses, but I appreciate the additional detail, particularly with respect to the PARITY/AC0 comment. $\endgroup$ – Philip White Nov 18 '10 at 2:37

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.