12
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ $\mathsf{NP} \subset \mathsf{P/poly}$ $\endgroup$ – Thomas supports Monica Jun 4 '15 at 5:11
  • 3
    $\begingroup$ coNP $\subset$ NP/poly $\;$ $\endgroup$ – user6973 Jun 4 '15 at 10:40
  • 4
    $\begingroup$ BH collapses $ $ $\endgroup$ – Emil Jeřábek 3.0 Jun 4 '15 at 12:37
  • 2
    $\begingroup$ GI is $NP$-hard $\endgroup$ – Mohammad Al-Turkistany Jun 4 '15 at 12:52
  • $\begingroup$ @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.) $\endgroup$ – Joshua Grochow Oct 22 '17 at 15:29
11
$\begingroup$

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]
$\endgroup$
7
$\begingroup$

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)

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You mean is rather than is not. $\endgroup$ – Emil Jeřábek 3.0 Nov 24 '17 at 7:40
  • $\begingroup$ @EmilJeřábek Yes. I am sorry for the mistake. I have corrected it now. Thanks for pointing it out. $\endgroup$ – Pawan Kumar Nov 24 '17 at 11:59
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tayfun Pay Nov 30 '17 at 16:43
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Here are some succinct ones:

  1. $PSPACE \subseteq P/poly$.
  2. $EXP \subseteq P/poly$.
  3. $NP \subseteq P/log$.
$\endgroup$
  • $\begingroup$ You can even add these to the answer: $NEXP \subseteq P/poly$, $P^{\#P} \subseteq P/poly$. $\endgroup$ – Pawan Kumar Nov 29 '17 at 4:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek 3.0 Nov 30 '17 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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