L'existence de problèmes PH-complets se relativise-t-elle?

12

Le résultat de Baker-Gill-Solovay a montré que la question P = NP ne se relativise pas, en ce sens qu'aucune preuve relativisante (insensible à la présence d'un oracle) ne peut régler la question P = NP.

Ma question est: Y a-t-il un résultat similaire pour la question, "Existe-t-il un problème de PH-complet?" Une réponse négative à cette question impliquerait P! = NP; une réponse affirmative serait peu probable mais intéressante car elle signifierait que le PH s'effondre à un certain niveau.

Je ne suis pas sûr, mais je soupçonne qu'un oracle TQBF conduirait PH à être égal à PSPACE, et donc à avoir un problème complet. En plus d'être incertain à ce sujet, je suis curieux de savoir s'il existe ou non un oracle par rapport auquel PH n'a pas, de manière prouvée, de problème complet.

-Philippe

cc.complexity-theory complexity-classes Philip White
la source

16

Yao a montré, en 1985, qu'il existe des oracles par rapport auxquels la hiérarchie polynomiale est infinie. Par rapport à un tel oracle, il n'existe pas de problèmes de PH-complet.

De plus, vous avez raison qu'avec un oracle TQBF, PH est égal à PSPACE. En fait, même P = PSPACE en présence d'un oracle TQBF.

Srikanth
la source

Merci, c'était la première réponse à laquelle j'ai répondu précisément à ma question.

Philip White

Σ_{k} P^{A}

$\Sigma_k P^A$

A

$A$

k

$k$

A

$A$

Σ_{k} P

$\Sigma_k P$

Π_{k} P

$\Pi_k P$

14

$L$ $L \in \Sigma_k P$ $k$ $PH = \Sigma_k P$ $PH$ $PH = \Sigma_k P$ $k$ $\Sigma_k SAT$

$AC^0$ $k$ $PH$ $\Sigma_k P$

Joshua Grochow
la source

Merci, cette réponse est également utile. Je pense que je savais qu'il a des problèmes complets s'il s'effondre, mais j'apprécie les détails supplémentaires, en particulier en ce qui concerne le commentaire PARITY / AC0.

Philip White

L'existence de problèmes PH-complets se relativise-t-elle?

Réponses: