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$

2 Answers 2

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$
2
  • $\begingroup$ Thanks, this was the first answer the precisely answered my question. $\endgroup$
    – user1338
    Nov 18, 2010 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$ Dec 26, 2012 at 17:23
13
$\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$
1
  • $\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$
    – user1338
    Nov 18, 2010 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.