# Does the existence of PH-complete problems relativize?

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

• 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.) Dec 26, 2012 at 17:23
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.