¿La existencia de problemas de PH completa se relativiza?

El resultado de Baker-Gill-Solovay mostró que la pregunta P = NP no se relativiza, en el sentido de que ninguna prueba relativizante (insensible a la presencia de un oráculo) puede resolver la pregunta P = NP.

Mi pregunta es: ¿Hay un resultado similar para la pregunta "¿Existe un problema de PH completo?" Una respuesta negativa a esta pregunta implicaría P! = NP; Una respuesta afirmativa sería poco probable pero interesante porque significaría que el PH colapsa a cierto nivel.

No estoy seguro, pero sospecho que un oráculo TQBF conduciría a que PH sea igual a PSPACE y, por lo tanto, tenga un problema completo. Además de no estar seguro de esto, tengo curiosidad por saber si existe o no un oráculo con respecto al cual el PH probablemente no tenga un problema completo.

-Philip

Yao demostró, en 1985, que existen oráculos con respecto a los cuales la Jerarquía Polinómica es infinita. En relación con tal oráculo, no existen problemas de PH completo.

Además, tiene razón en que con un oráculo TQBF, PH es igual a PSPACE. De hecho, incluso P = PSPACE en presencia de un oráculo TQBF.

PH tiene problemas completos si y sólo si se derrumba: si tiene un problema completo , entonces para algunos , de modo . Por el contrario, si es finito, entonces para algunos , y es entonces PH-completo.$L$$L \in \Sigma_k P$$k$$PH = \Sigma_k P$$PH$$PH = \Sigma_k P$$k$$\Sigma_k SAT$

Como señaló Srikanth, hay oráculos en relación con los cuales el PH es infinito. (De hecho, encontrar tales oráculos fue parte de la razón por la cual las personas comenzaron a mirar PARITY no en en primer lugar). Usando técnicas similares basadas en circuitos, también hay, para cada , un oráculo que colapsa el exactamente ( Ker-I Ko, SICOMP 18 (2), 1989 ). Para aquellos que estén interesados, recomiendo la encuesta de Ker-I Ko .$AC^0$$k$$PH$$\Sigma_k P$