Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

Question

What are some (not well-known) assertions that if true, the PH must collapse?

Replies containing a short high-level assertion with reference(s) are appreciated. I tried to reverse-search without much luck.

Answer 1

There are a (growing) number of parameterized complexity results where the existence of a polynomial-sized kernelization implies the collapse of the PH to the third level. The central technique is given in [1], building on prior work (referenced in [1]).

As a simple example, the $k$-Path problem is the parameterized version of the Longest Path problem:

$k$-Path
Instance: A graph $G$ and integer $k$.
Parameter: $k$.
Question: Does $G$ contain a path of length $k$?

This problem is in FPT (with somewhat practical algorithms), but in [2] they show that if it has a polynomially sized kernel (in $k$), then the PH collapses to $\Sigma^{P}_{3}$. (The current presentation is typically phrased as a negative kernalization result unless NP $\subseteq$ coNP/poly or coNP $\subseteq$ NP/poly, so searching for something like "no polynomial kernel unless" nets a lot of results.)

References

1. H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, "Kernelization lower bounds by cross-composition", SIAM J. Discrete Math., 28 (2014), pp. 277–305. [arXiv version]
2. H. L. Bodlaender, R. G. Downey, M. R. Fellows, D. Hermelin, "On problems without polynomial kernels", Journal of Computer and System Sciences, 75(8):423-434. 2009. [Stanford hosted version]

Answer 2

Here is another interesting condition under which Polynomial-hierarchy collapses to third level: Suppose an NP-complete language has a random self-reduction (non-adaptive), Then the polynomial hierarchy collapses to $\Sigma_{3}^{P}$. For reference: Look at Luca Trevisan's Notes. (Theorem 67)

Answer 3

The collapse of PH is implied by the collapse of the Boolean hierarchy. The original result is due to Kadin [1]; it was refined by Chang and Kadin [2] to show that $$\mathrm{BH}=\mathrm{BH}_k\implies\mathrm{PH}=\mathrm{BH}^\mathrm{NP}_k.$$

References:

[1] Jim Kadin, The polynomial time hierarchy collapses if the Boolean hierarchy collapses, SIAM Journal on Computing 17 (1988), no. 6, pp. 1263–1282, doi: 10.1137/0217080.

[2] Richard Chang and Jim Kadin, The Boolean hierarchy and the polynomial hierarchy: a closer connection, SIAM Journal on Computing 25 (1996), no. 2, pp. 340–354, doi: 10.1137/S0097539790178069.

Answer 4

Another interesting condition is this:

We know that approximating $\#3SAT$ is in $BPP^{NP}$ (Now $BPP$ in $\Sigma_2^{P}$ makes approximating $\#3SAT$ in $\Sigma_3^{P}$).

Also, By Toda's theorem, $PH \subseteq P^{\#P}$.

Combining these two, we get: If approximating $\#3SAT$ is equivalent to computing $\#3SAT$ exactly, then Polynomial Hierarchy collapses.

Answer 5

Computing unique solutions to $\mathsf{NP}$ problems collapses $\mathsf{PH}$ (Hemaspaandra-Naik-Ogihara-Selman), but you have to be a little careful about how you formalize this statement. (For example, it is not known whether $\mathsf{NP}=\mathsf{UP}$ collapses $\mathsf{PH}$.) One formalization is as follows:

Suppose there is an $L \in \mathsf{NP}$ such that for every 3SAT formula $\varphi$, if $\varphi$ is unsatisfiable then there is no $x$ such that $(\varphi,x) \in L$, and if $\varphi$ is satisfiable, then there is a unique $x$ such that $(\varphi,x) \in L$. Then $\mathsf{PH}$ collapses.

Another formalization is:

$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$ implies $\mathsf{PH}$ collapses.

Answer 6

There is a large selection of results that hold assuming PH does not collapse. Let $A := \forall i , \Sigma^{P}_{i} \neq \Pi^{P}_{i}$, i.e. $\mathbb{PH}$ does not collapse. Then such results can then be summarized as $A \implies B$, where B is the result proven.

By a simple contrapositive, any such result is equivalent to $ \bar{B} \implies \bar{A}$, i.e. if the result does not hold unconditionally, then $\mathbb{PH}$ must also collapse. Historically, those results served two purposes:

1. To increase confidence to the intuition that $\mathbb{PH}$ does not collapse, by showing that it implies results that we believe to be true (or equivalently by contrapositive, that unlikely results imply a collapse).
2. To establish a web of results that are true, if one accepts $\mathbb{PH}$ does not collapse, without the need to wait for a proof of that result. i.e. to establish conditional results.

Note: It is also not unusual that papers assume that $\mathbb{PH}$ does not collapse in addition to some other hypothesis, e.g. the (generalized) Riemann hypothesis. Then, the contrapositive simply shows that at least one of the hypothesis is false.

Answer 7

Here are some succinct ones:

1. $PSPACE \subseteq P/poly$.
2. $EXP \subseteq P/poly$.
3. $NP \subseteq P/log$.