<p>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]).</p>

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

<blockquote>
  <p><strong>$k$-Path</strong><br/>
  <em>Instance</em>: A graph $G$ and integer $k$.<br/>
  <em>Parameter</em>: $k$.<br/>
  <em>Question</em>: Does $G$ contain a path of length $k$?</p>
</blockquote>

<p>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.)</p>

<p><strong>References</strong></p>

<ol>
<li>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. <a href="http://arxiv.org/pdf/1206.5941v1.pdf" rel="noreferrer">[arXiv version]</a></li>
<li>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. <a href="http://web.stanford.edu/~rrwill/presentations/no-poly-kernels.pdf" rel="noreferrer">[Stanford hosted version]</a></li>
</ol>

CC BY-SA 3.0
2015-06-05T01:44:46.853Z
2017-10-22T08:28:31.233Z
2017-10-22T08:28:31.233Z
Luke Mathieson
<p>Here is another <strong>interesting condition</strong> 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 <a href="https://people.eecs.berkeley.edu/~luca/notes/complexitynotes02.pdf" rel="nofollow noreferrer">Luca Trevisan's Notes</a>. (Theorem 67)</p>

CC BY-SA 3.0
2017-10-22T03:43:16.020Z
2017-11-25T04:24:38.127Z
2017-11-25T04:24:38.127Z
Pawan Kumar
<p>The collapse of PH is implied by the collapse of the <a href="https://en.wikipedia.org/wiki/Boolean_hierarchy" rel="noreferrer">Boolean hierarchy</a>. 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.$$</p>

<p><strong>References:</strong></p>

<p>[1] Jim Kadin, <em>The polynomial time hierarchy collapses if the Boolean hierarchy collapses</em>, SIAM Journal on Computing 17 (1988), no. 6, pp. 1263–1282, doi: <a href="https://doi.org/10.1137/0217080" rel="noreferrer">10.1137/0217080</a>.</p>

<p>[2] Richard Chang and Jim Kadin, <em>The Boolean hierarchy and the polynomial hierarchy: a closer connection</em>, SIAM Journal on Computing 25 (1996), no. 2, pp. 340–354, doi: <a href="https://doi.org/10.1137/S0097539790178069" rel="noreferrer">10.1137/S0097539790178069</a>.</p>

CC BY-SA 3.0
2017-10-23T15:01:01.333Z
2017-10-23T15:01:01.333Z
Emil Jeřábek
<p>Another interesting condition is this: </p>

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

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

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

CC BY-SA 3.0
2017-11-24T11:59:59.983Z
@EmilJeřábek Yes. I am sorry for the mistake. I have corrected it now. Thanks for pointing it out.
Pawan Kumar
CC BY-SA 3.0
2017-11-24T05:56:28.273Z
2017-11-24T11:59:11.517Z
2017-11-24T11:59:11.517Z
Pawan Kumar
<p>Computing unique solutions to $\mathsf{NP}$ problems collapses $\mathsf{PH}$ (<a href="http://dx.doi.org/10.1137/S0097539794268315" rel="noreferrer">Hemaspaandra-Naik-Ogihara-Selman</a>), but you have to be a little careful about how you formalize this statement. (For example, it is <em>not</em> known whether $\mathsf{NP}=\mathsf{UP}$ collapses $\mathsf{PH}$.) One formalization is as follows:</p>

<blockquote>
  <p>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 <em>unique</em> $x$ such that $(\varphi,x) \in L$. Then $\mathsf{PH}$ collapses.</p>
</blockquote>

<p>Another formalization is:</p>

<blockquote>
  <p>$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$ implies $\mathsf{PH}$ collapses.</p>
</blockquote>

CC BY-SA 3.0
2017-11-30T16:43:33.270Z
In this case, "unique" means that the output of machine $N$ on some path is either no or some set of 0's and 1's, but this set of 0's and 1's are the same on each path that does not say no.
Tayfun Pay
CC BY-SA 3.0
2017-11-27T14:28:52.050Z
2017-11-27T14:28:52.050Z
Joshua Grochow
<p>Here are some succinct ones:</p>

<ol>
<li>$PSPACE \subseteq P/poly$.</li>
<li>$EXP \subseteq P/poly$.</li>
<li>$NP \subseteq P/log$.  </li>
</ol>

CC BY-SA 3.0
2017-11-29T04:03:00.963Z
You can even add these to the answer: $NEXP \subseteq P/poly$, $P^{\#P} \subseteq P/poly$.
Pawan Kumar
CC BY-SA 3.0
2017-11-30T17:06:34.623Z
All of these are subsumed by the obvious answer “$\mathrm{NP\subseteq P/poly}$”, given in the very first comment to the question. This answer does not bring anything new.
Emil Jeřábek
CC BY-SA 3.0
2017-10-24T05:06:37.677Z
2017-10-24T05:06:37.677Z
Ainesh Bakshi
<p>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. </p>

<p>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:</p>

<ol>
<li>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).</li>
<li>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.</li>
</ol>

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

CC BY-SA 3.0
2015-06-04T08:51:55.237Z
2015-06-04T08:51:55.237Z
chazisop
<p>What are some (not well-known) assertions that if true, the PH must collapse?</p>

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

CC BY-SA 3.0
2015-06-04T05:11:19.417Z
$\mathsf{NP} \subset \mathsf{P/poly}$
Thomas Steinke
CC BY-SA 3.0
2015-06-04T12:37:05.830Z
BH collapses $ $
Emil Jeřábek
CC BY-SA 3.0
2015-06-04T12:52:34.117Z
GI is $NP$-hard
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-10-22T15:29:08.337Z
@Emil: I think that one may be sufficiently not well-known to count as an answer. (The other comments so far are of course useful, but pretty standard in grad complexity courses.)
Joshua Grochow
CC BY-SA 3.0
2017-10-23T15:01:31.263Z
@JoshuaGrochow Right. I posted it as an answer now.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><big-list>
Sufficient conditions for the collapse of Polynomial Hierarchy (PH)
user34344
# Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

(Asked by: username_0 on 2015-06-04)

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.

**Tags:** cc.complexity-theory, complexity-classes, big-list
> **Comments:**
> **username_1**: $\mathsf{NP} \subset \mathsf{P/poly}$  
> **username_2**: BH collapses $ $  
> **username_3**: GI is $NP$-hard  
> **username_4**: @Emil: I think that one may be sufficiently not well-known to count as an answer. (The other comments so far are of course useful, but pretty standard in grad complexity courses.)  
> **username_2**: @JoshuaGrochow Right. I posted it as an answer now.  

---

## 7 answers

### Answer by username_5 on 2015-06-05. Score: 12

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]](http://arxiv.org/pdf/1206.5941v1.pdf)
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]](http://web.stanford.edu/~rrwill/presentations/no-poly-kernels.pdf)


---

### Answer by username_6 on 2017-10-22. Score: 8

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](https://people.eecs.berkeley.edu/~luca/notes/complexitynotes02.pdf). (Theorem 67)


---

### Answer by username_2 on 2017-10-23. Score: 7

The collapse of PH is implied by the collapse of the [Boolean hierarchy](https://en.wikipedia.org/wiki/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](https://doi.org/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](https://doi.org/10.1137/S0097539790178069).


---

### Answer by username_6 on 2017-11-24. Score: 7

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.

> **Comments:**
> **username_6**: @EmilJeřábek Yes. I am sorry for the mistake. I have corrected it now. Thanks for pointing it out.  

---

### Answer by username_4 on 2017-11-27. Score: 5

Computing unique solutions to $\mathsf{NP}$ problems collapses $\mathsf{PH}$ ([Hemaspaandra-Naik-Ogihara-Selman](http://dx.doi.org/10.1137/S0097539794268315)), 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.

> **Comments:**
> **username_7**: In this case, "unique" means that the output of machine $N$ on some path is either no or some set of 0's and 1's, but this set of 0's and 1's are the same on each path that does not say no.  

---

### Answer by username_8 on 2017-10-24. Score: 4

Here are some succinct ones:

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

> **Comments:**
> **username_6**: You can even add these to the answer: $NEXP \subseteq P/poly$, $P^{\#P} \subseteq P/poly$.  
> **username_2**: All of these are subsumed by the obvious answer “$\mathrm{NP\subseteq P/poly}$”, given in the very first comment to the question. This answer does not bring anything new.  

---

### Answer by username_9 on 2015-06-04. Score: 4

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.


---

