Does the existence of PH-complete problems relativize?

Question

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

Answer 1

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.

Answer 2

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.