¿Se sabe que el colapso de

Contenidos entre cada nivel de la jerarquía polinómica hay varias clases de complejidad, que incluyen , , y . Por falta de una mejor terminología, me referiré a estas y a otras como clases intermedias entre los niveles e en la jerarquía polinómica. Para los propósitos de esta pregunta, suponga que son las clases contenidas en $\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}$ pero contienen y / o . Queremos evitar incluir , si es posible, ya que es trivialmente equivalente a si colapsa al nivel . $\Sigma_i^\text{P}$ $\Pi_i^\text{P}$ $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ $\text{PH}$ ${i+1}^{th}$

Además, defina lo siguiente:
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$

Lo anterior es una generalización de la clase (también escrita ). En esta definición, es equivalente a . Se considera en otra pregunta cstheory.se . Es fácil ver que y contiene tanto como . $\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}$

Diagrama de referencia:

Diagrama de PH

Pregunta:
Suponga que la jerarquía polinómica se colapsa al nivel , pero no colapsa al nivel . Es decir, y . ${i+1}^{th}$ $i^{th}$ $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$

¿Podemos decir algo más sobre las relaciones entre estas clases intermedias y otras en cualquier nivel por debajo de ? ¿Existe un esquema para una colección de clases de complejidad donde, para cada colección, las clases son equivalentes si y solo si el colapsa exactamente a un nivel elegido arbitrariamente? $i+1$ $\text{PH}$

Solo como seguimiento, suponga que la jerarquía colapsó en una de estas clases intermedias en particular (como ). Dependiendo de la clase seleccionada, sabemos si este colapso debe continuar extenderse hacia abajo, tal vez incluso a la nivel? $\Delta_{i+1}^{\text{P}}$ $i^{th}$

La pregunta anterior fue parcialmente explorada y respondida en un documento de Hemaspaandra et. al:
Un colapso descendente dentro de la jerarquía polinómica
¿Alguien sabe de ejemplos adicionales que no se mencionan en este documento o tiene una intuición adicional de lo que debe suceder para que una clase logre esto?

cc.complexity-theory polynomial-hierarchy mdxn
fuente

Respuestas:

No tengo una buena respuesta, pero en el espíritu de complejidad, tengo algunas respuestas que sugieren que una buena respuesta puede ser difícil de encontrar :).

$\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}$
$\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$
$\mathsf{BPH}$ $\mathsf{PH}$ $\mathsf{PH}$
$\mathsf{PH}$ $\mathsf{DP}$ $k$ $\mathsf{PH}$ $k$ $\mathsf{\Sigma_2 P}$

Joshua Grochow
fuente

Σ_{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}?$

Σ_{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$