L'effondrement de

Entre chaque niveau de la hiérarchie polynomiale se trouvent différentes classes de complexité, notamment , , et . Faute d'une meilleure terminologie, je les qualifierai, ainsi que d'autres, de classes intermédiaires entre les niveaux et dans la hiérarchie polynomiale. Aux fins de cette question, supposons que ce sont les classes contenues dans mais contiennent et / ou . Nous voulons éviter d'inclure $\Delta_i^{\text{P}}$ $\text{DP}$ $\text{BH}_k$ $\Sigma_i^\text{P} \cap \Pi_i^\text{P}$ $i$ $i+1$ $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ $\Sigma_i^\text{P}$ $\Pi_i^\text{P}$ $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ , si possible, car il est trivialement équivalent à s'il s'effondre en niveau. $\text{PH}$ ${i+1}^{th}$

De plus, définissez les éléments suivants:
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$

Ce qui précède est une généralisation de la classe (également écrite ). Dans cette définition, est équivalent à . Il est considéré dans une autre question cstheory.se . Il est facile de voir que et contient à la fois et . $\text{DP}$ $\text{D}^\text{P}$ $\text{DP}$ $\text{DP}_1$ $\text{DP}_i \subseteq \Delta_{i+1}^{\text{P}}$ $\Sigma_i^\text{P}$ $\Pi_i^\text{P}$

Diagramme de référence:

Diagramme de PH

Question:
Supposons que la hiérarchie polynomiale s'effondre au niveau , mais ne s'effondre pas au niveau . Autrement dit, et . ${i+1}^{th}$ $i^{th}$ $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$

Pouvons-nous en dire plus sur les relations entre ces classes intermédiaires elles-mêmes et les autres à tout niveau inférieur à ? Existe-t-il un schéma pour une collection de classes de complexité où, pour chaque collection, les classes sont équivalentes si et seulement si le s'effondre exactement à un niveau choisi arbitrairement? $i+1$ $\text{PH}$

À titre de suivi, supposons que la hiérarchie s'est effondrée à l'une quelconque de ces classes intermédiaires (telles que ). Selon la classe choisie, savons-nous si cet effondrement doit continuer à s'étendre vers le bas, peut-être même au niveau ? $\Delta_{i+1}^{\text{P}}$ $i^{th}$

La question ci-dessus a été partiellement explorée et répondue dans un document de Hemaspaandra et. al:
un effondrement vers le bas au sein de la hiérarchie polynomiale.
Quelqu'un connaît-il des exemples supplémentaires non mentionnés dans cet article ou a-t-il une intuition supplémentaire de ce qui doit se produire pour qu'une classe puisse accomplir cela?

cc.complexity-theory polynomial-hierarchy mdxn
la source

Réponses:

Je n'ai pas de bonne réponse, mais dans un esprit de complexité, j'ai quelques réponses qui suggèrent qu'une bonne réponse peut être difficile à trouver :).

Notez que la version généralisée du théorème de Ladner implique qu'il y a une infinité de degrés poly-temps strictement entre et tout degré poly-temps strictement au-dessus. En particulier, si la hiérarchie s'effondre au niveau -st mais pas au -th, alors il y a une infinité de p-degrés entre et . $\mathsf{\Sigma_i P}$ $i+1$ $i$ $\mathsf{\Sigma_i P}$ $\mathsf{\Sigma_{i+1} P} \cap \mathsf{\Pi_{i+1} P}=\mathsf{\Sigma_{i+1} P}$
Si je me souviens bien, construire un oracle pour lequel ressemble à la hiérarchie arithmétique est toujours un problème ouvert. Par "ressemble à la hiérarchie arithmétique", je veux dire que ne s'effondre pas et pour tous les . Cela suggère au moins que la réponse à votre question peut ne pas être connue. $\mathsf{PH}$ $\mathsf{PH}$ $\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_{k+1} P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}$ $k$
Ker-I Ko donne des oracles dans lesquels il sépare les niveaux de de ceux de . Comme ces deux hiérarchies s'entrelacent, cela vous donne au moins quelques informations sur les effondrements relativisables de problèmes entre les niveaux de . $\mathsf{BPH}$ $\mathsf{PH}$ $\mathsf{PH}$
Cette prochaine référence n'est pas la bonne direction, mais vous pourriez également être intéressé par le résultat et ses techniques. Chang et Kadin ont montré que si la hiérarchie booléenne (qui vit entièrement en dessous du deuxième niveau de , mais étend à toute une hiérarchie) s'effondre à son niveau ème alors s'effondre au niveau -ème de la hiérarchie booléenne sur . $\mathsf{PH}$ $\mathsf{DP}$ $k$ $\mathsf{PH}$ $k$ $\mathsf{\Sigma_2 P}$

Joshua Grochow
la source

Doit be

Σ_{k} P \cup Π_{k} P ⊊ Δ_{k} P = Σ_{k + 1} P \cap Π_{k + 1} P

$\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_k P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}$

Δ_{k} P = Σ_{k} P \cup Π_{k} P ⊊ Δ_{k + 1} P = Σ_{k + 1} P \cap Π_{k + 1} P ?

$\mathsf{\Delta_{k} P}=\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_{k+1} P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}?$

T ....

désolé mais j'ai pensé correct? Par exemple:

Σ_{k - 1}^{P} \cup Π_{k - 1}^{P} \subseteq Δ_{k}^{P} \subseteq Σ_{k}^{p} \cap Π_{k}^{P} \subseteq Σ_{k}^{P} \cup Π_{k}^{P}

$\Sigma_{k-1}^P\cup\Pi_{k-1}^P\subseteq \Delta_k^P\subseteq \Sigma_k^p\cap\Pi_k^P\subseteq \Sigma_k^P\cup\Pi_k^P$

P = Σ_{0}^{P} \cup Π_{0}^{P} = P \cup P \subseteq Δ_{1}^{P} = P \subseteq Σ_{1}^{p} \cap Π_{1}^{P} = N P \cap c o N P \subseteq Σ_{1}^{P} \cup Π_{1}^{P} = N P \cup c o N P \subseteq Δ_{2}^{P} = P^{N P} \subseteq Σ_{2}^{P} \cap Π_{2}^{P} \subseteq Σ_{2}^{P} \cup Π_{2}^{P} \dots

$P=\Sigma_{0}^P\cup\Pi_{0}^P=P\cup P\subseteq \Delta_1^P=P\subseteq \Sigma_1^p\cap\Pi_1^P=NP\cap coNP\subseteq \Sigma_1^P\cup\Pi_1^P=NP\cup coNP\subseteq \Delta_2^P=P^{NP}\subseteq\Sigma_2^P\cap\Pi_2^P\subseteq\Sigma_2^P\cup\Pi_2^P\dots$

T ....