13
$\begingroup$

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. 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

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
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?

$\endgroup$

1 Answer 1

12
$\begingroup$

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 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 showed that if the Boolean hierarchy (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}$.

$\endgroup$
2
  • 1
    $\begingroup$ 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}?$$ $\endgroup$
    – Turbo
    Jul 8, 2017 at 23:43
  • 1
    $\begingroup$ 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$$ $\endgroup$
    – Turbo
    Jul 9, 2017 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.