<p>I don't have a good answer, but in the spirit of complexity, I have some answers which suggest that a good answer may be hard to come by :).</p>

<ol>
<li><p>Note that the generalized version of Ladner's Theorem implies that there are infinitely many poly-time degrees strictly in between $\mathsf{\Sigma_i P}$ and any poly-time degree strictly above it. In particular, if the hierarchy collapses to the $i+1$-st level but not the $i$-th, then there are infinitely many p-degrees between $\mathsf{\Sigma_i P}$ and $\mathsf{\Sigma_{i+1} P} \cap \mathsf{\Pi_{i+1} P}=\mathsf{\Sigma_{i+1} P}$.</p></li>
<li><p>If I recall correctly, constructing an oracle for which $\mathsf{PH}$ looks like the arithmetic hierarchy is still an open problem. By "looks like the arithmetic hierarchy," I mean that $\mathsf{PH}$ does not collapse, and $\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}$ for all $k$. This at least suggests that the answer to your question may not be known.</p></li>
<li><p><a href="http://www.cs.sunysb.edu/~keriko/survey2.pdf" rel="nofollow noreferrer">Ker-I Ko</a> gives oracles in which he separates the levels of $\mathsf{BPH}$ from those of $\mathsf{PH}$. As these two hierarchies intertwine one another, this gives you at least some information about relativizable collapses of problems between the levels of $\mathsf{PH}$.</p></li>
<li><p>This next reference is the wrong direction, but you might also be interested in the result and its techniques. <a href="http://www.csee.umbc.edu/~chang/papers/closer/bhe2.pdf" rel="nofollow noreferrer">Chang and Kadin</a> showed that if the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bh" rel="nofollow noreferrer">Boolean hierarchy</a> (which lives entirely below the second level of $\mathsf{PH}$, but extends $\mathsf{DP}$ to a whole hierarchy) collapses to its $k$-th level then $\mathsf{PH}$ collapses to the $k$-th level of the Boolean hierarchy over $\mathsf{\Sigma_2 P}$. </p></li>
</ol>

CC BY-SA 3.0
2017-07-08T23:43:27.760Z
Should $$\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}$$ be $$\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}?$$
Turbo
CC BY-SA 3.0
2017-07-09T00:27:52.803Z
sorry but I thought $\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$ correct?

Eg: $$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$$
Turbo
CC BY-SA 3.0
2013-10-08T14:56:17.527Z
2017-07-09T21:54:44.817Z
2017-07-09T21:54:44.817Z
Joshua Grochow
<p>Contained in-between each level of the polynomial hierarchy are various complexity classes, including $\Delta_i^{\text{P}}$, $\text{DP}$, $\text{BH}_k$, and $\Sigma_i^\text{P} \cap \Pi_i^\text{P}$. For lack of better terminology, I will refer to these and any others as <em>intermediate classes</em> between levels $i$ and $i+1$ in the polynomial hierarchy. For the purposes of this question, assume they are the classes contained in $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ but contain $\Sigma_i^\text{P}$ and/or $\Pi_i^\text{P}$. We want to avoid including $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$, if possible, as it is trivially equivalent to $\text{PH}$ if it collapses to the ${i+1}^{th}$ level.</p>

<p>In addition, define the following:<br>
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$  </p>

<p>The above is a generalization of the class $\text{DP}$ (also written $\text{D}^\text{P}$). In this definition, $\text{DP}$ is equivalent to $\text{DP}_1$. It is considered in another <a href="https://cstheory.stackexchange.com/questions/18147/an-analog-of-dp-for-the-second-level-of-the-polynomial-hierarchy">cstheory.se question</a>. It is easy to see that $\text{DP}_i \subseteq \Delta_{i+1}^{\text{P}}$ and contains both $\Sigma_i^\text{P}$ and $\Pi_i^\text{P}$.</p>

<p><strong>Reference Diagram:</strong>  </p>

<p><img src="https://i.sstatic.net/kWnPz.png" alt="Diagram of PH"></p>

<p><strong>Question:</strong><br>
Suppose that the polynomial hierachy collapses to the ${i+1}^{th}$ level, but does <strong>not</strong> collapse to the $i^{th}$ level.  That is, $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ and $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$.</p>

<p>Can we say anything more about the relationships between these intermediate classes themselves and others in any level below $i+1$? Is there a schema for a collection of complexity classes where, for every collection, the classes are equivalent if and only if the $\text{PH}$ collapses exactly to an arbitrarily chosen level?</p>

<p>Just as a followup, suppose that the hierarchy collapsed to any particular one of these intermediate classes (such as $\Delta_{i+1}^{\text{P}}$). Depending on the class selected, do we know if this collapse must continue to extend downwards, perhaps even to the $i^{th}$ level?</p>

<p>The above question was partially explored and answered in a paper by Hemaspaandra et. al:<br>
<a href="http://arxiv.org/pdf/cs/9910007v1.pdf" rel="nofollow noreferrer">A Downward Collapse within the Polynomial Hierarchy</a><br>
Does someone happen to know of additional examples not mentioned in this paper or have further intuition as to what needs to happen in order for a class to accomplish this?</p>

<cc.complexity-theory><polynomial-hierarchy>
Is the collapse of $PH$ known to extend downward to classes in-between its levels?
mdxn
# Is the collapse of $PH$ known to extend downward to classes in-between its levels?

(Asked by: username_0 on 2013-10-08)

Contained in-between each level of the polynomial hierarchy are various complexity classes, including $\Delta\_i^{\text{P}}$, $\text{DP}$, $\text{BH}\_k$, and $\Sigma\_i^\text{P} \cap \Pi\_i^\text{P}$. For lack of better terminology, I will refer to these and any others as *intermediate classes* between levels $i$ and $i+1$ in the polynomial hierarchy. For the purposes of this question, assume they are the classes contained in $\Sigma\_{i+1}^\text{P} \cap \Pi\_{i+1}^\text{P}$ but contain $\Sigma\_i^\text{P}$ and/or $\Pi\_i^\text{P}$. We want to avoid including $\Sigma\_{i+1}^\text{P} \cap \Pi\_{i+1}^\text{P}$, if possible, as it is trivially equivalent to $\text{PH}$ if it collapses to the ${i+1}^{th}$ level.

In addition, define the following:  
$\text{DP}\_i = \left \{ L \cap L' : L \in \Sigma\_i^\text{P} \text{ and } L' \in \Pi\_i^{\text{P}} \right \}$

The above is a generalization of the class $\text{DP}$ (also written $\text{D}^\text{P}$). In this definition, $\text{DP}$ is equivalent to $\text{DP}\_1$. It is considered in another [cstheory.se question](https://cstheory.stackexchange.com/questions/18147/an-analog-of-dp-for-the-second-level-of-the-polynomial-hierarchy). It is easy to see that $\text{DP}\_i \subseteq \Delta\_{i+1}^{\text{P}}$ and contains both $\Sigma\_i^\text{P}$ and $\Pi\_i^\text{P}$.

**Reference Diagram:**

![Diagram of PH](https://i.sstatic.net/kWnPz.png)

**Question:**  
Suppose that the polynomial hierachy collapses to the ${i+1}^{th}$ level, but does **not** collapse to the $i^{th}$ level. That is, $\Sigma\_{i+1}^\text{P}=\Pi\_{i+1}^\text{P}$ and $\Sigma\_{i}^\text{P}\neq\Pi\_{i}^\text{P}$.

Can we say anything more about the relationships between these intermediate classes themselves and others in any level below $i+1$? Is there a schema for a collection of complexity classes where, for every collection, the classes are equivalent if and only if the $\text{PH}$ collapses exactly to an arbitrarily chosen level?

Just as a followup, suppose that the hierarchy collapsed to any particular one of these intermediate classes (such as $\Delta\_{i+1}^{\text{P}}$). Depending on the class selected, do we know if this collapse must continue to extend downwards, perhaps even to the $i^{th}$ level?

The above question was partially explored and answered in a paper by Hemaspaandra et. al:  
[A Downward Collapse within the Polynomial Hierarchy](http://arxiv.org/pdf/cs/9910007v1.pdf)  
Does someone happen to know of additional examples not mentioned in this paper or have further intuition as to what needs to happen in order for a class to accomplish this?

**Tags:** cc.complexity-theory, polynomial-hierarchy

---

## 1 answers

### Answer by username_1 on 2013-10-08. Score: 13 | Accepted answer

I don't have a good answer, but in the spirit of complexity, I have some answers which suggest that a good answer may be hard to come by :).

1. Note that the generalized version of Ladner's Theorem implies that there are infinitely many poly-time degrees strictly in between $\mathsf{\Sigma\_i P}$ and any poly-time degree strictly above it. In particular, if the hierarchy collapses to the $i+1$-st level but not the $i$-th, then there are infinitely many p-degrees between $\mathsf{\Sigma\_i P}$ and $\mathsf{\Sigma\_{i+1} P} \cap \mathsf{\Pi\_{i+1} P}=\mathsf{\Sigma\_{i+1} P}$.
2. If I recall correctly, constructing an oracle for which $\mathsf{PH}$ looks like the arithmetic hierarchy is still an open problem. By "looks like the arithmetic hierarchy," I mean that $\mathsf{PH}$ does not collapse, and $\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}$ for all $k$. This at least suggests that the answer to your question may not be known.
3. [Ker-I Ko](http://www.cs.sunysb.edu/~keriko/survey2.pdf) gives oracles in which he separates the levels of $\mathsf{BPH}$ from those of $\mathsf{PH}$. As these two hierarchies intertwine one another, this gives you at least some information about relativizable collapses of problems between the levels of $\mathsf{PH}$.
4. This next reference is the wrong direction, but you might also be interested in the result and its techniques. [Chang and Kadin](http://www.csee.umbc.edu/~chang/papers/closer/bhe2.pdf) showed that if the [Boolean hierarchy](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bh) (which lives entirely below the second level of $\mathsf{PH}$, but extends $\mathsf{DP}$ to a whole hierarchy) collapses to its $k$-th level then $\mathsf{PH}$ collapses to the $k$-th level of the Boolean hierarchy over $\mathsf{\Sigma\_2 P}$.

> **Comments:**
> **username_2**: Should $$\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}$$ be $$\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}?$$  
> **username_2**: sorry but I thought $\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$ correct?  Eg: $$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$$  

---

