18
$\begingroup$

We know that if $P=NP$ then the whole PH collapses. What if the polynomial hierarchy collapses partially ? (Or how to understand that PH could collapse above a certain point and not below ?)

In shorter words, what would be the consequences of $NP=coNP$ and $P\ne NP$ ?

$\endgroup$
10
  • 4
    $\begingroup$ In that case PH still collapses (to the 1st rather than 0th level). $\endgroup$ Sep 5, 2011 at 1:15
  • $\begingroup$ Te first sentence seems to express that "we are in trouble if P=NP is not because the hierarchy collapses" which is not correct (putting aside possibly controversial issue of whether P=NP a troublesome situation or not). $\endgroup$
    – Kaveh
    Sep 5, 2011 at 3:47
  • 2
    $\begingroup$ @Huck I think OP might be trying to ask what are the consequences of PH collapsing to the 1st level. What cool problems would we be able to solve then? $\endgroup$ Sep 5, 2011 at 8:08
  • $\begingroup$ @Xavier: Why do you say "...and we are in trouble". P = NP, and the consequent PH collapse, would be just fantastic ;-) $\endgroup$ Sep 5, 2011 at 9:03
  • $\begingroup$ @ArtemKaznatcheev : tks to your understanding comment $\endgroup$ Sep 5, 2011 at 9:36

4 Answers 4

20
$\begingroup$

To me, one of the most basic and surprising consequences of $\mathsf{NP}=\mathsf{coNP}$ is the existence of short proofs for a whole host of problems where it is very difficult to see why they should have short proofs. (This is sort of taking a step back from "What other complexity implications does this collapse have?" to "What are the very basic, down-to-earth reasons this collapse would be surprising?")

For example, if $\mathsf{NP}=\mathsf{coNP}$, then for every graph that is not Hamiltonian, there is a short proof of that fact. Similarly for graphs that are not 3-colorable. Similarly for pairs of graphs that are not isomorphic. Similarly for any propositional tautology.

In a world where $\mathsf{P} \neq \mathsf{NP} = \mathsf{coNP}$, the difficulty in proving propositional tautologies isn't that some short tautologies have long proofs - because in such a world every tautology has a polynomially short proof - but rather that there is some other reason that we are unable to find those proofs efficiently.

$\endgroup$
3
  • $\begingroup$ I like this answer! +1 $\endgroup$
    – Tayfun Pay
    Feb 15, 2014 at 17:04
  • $\begingroup$ Tks for your answer, the underlined consequence is quite surprising. I wonder what kind of other reason unables to find those proofs efficiently. Any idea ? $\endgroup$ Feb 16, 2014 at 15:16
  • $\begingroup$ To expand on that last paragraph see "The Relative Efficiency of Propositional Proof Systems" $\endgroup$
    – AHusain
    Mar 12, 2021 at 3:27
13
$\begingroup$

If we also assume $\mathsf{NP}=\mathsf{RP}$, then the hypothesis would also cause the collapse of randomized classes: $\,\,\mathsf{ZPP}=\mathsf{RP}=\mathsf{CoRP}=\mathsf{BPP}$. Although these are all conjectured to unconditionally collapse into $\mathsf{P}$, anyway, it is still open whether that indeed happens. In any case, $\mathsf{NP}=co\mathsf{NP}$ does not seem to imply in itself that these randomized classes collapse.

If they do not, that is, we at least have $\mathsf{BPP}\neq \mathsf{P}$, then, along only with the $\mathsf{NP}=co\mathsf{NP}$ hypothesis, this would have another important consequence: $\,\,\mathsf{E}\neq \mathsf{NE}$. This follows from a result of Babai, Fortnow, Nisan and Wigderson, which says that if all unary (tally) languages in $\mathsf{PH}$ fall in $\mathsf{P}$, then $\mathsf{BPP}=\mathsf{P}$. Thus, if $\mathsf{BPP}\neq \mathsf{P}$, then they cannot all fall in $\mathsf{P}$, as the $\mathsf{NP}=co\mathsf{NP}$ assumption implies $\mathsf{PH}=\mathsf{NP}$. Therefore, there must be a tally language in $\mathsf{NP}-\mathsf{P}$. Finally, the presence of a tally language in $\mathsf{NP}-\mathsf{P}$ is well known to imply $\mathsf{E}\neq \mathsf{NE}$.

The above reasoning shows the interesting effect that the $\mathsf{NP}=co\mathsf{NP}$ hypothesis, despite being a collapse, actually amplifies the separating power of $\mathsf{BPP}\neq \mathsf{P}$, as the latter alone is not known to imply $\mathsf{E}\neq \mathsf{NE}$. This "anomaly" seems to support the conjecture $\mathsf{BPP}= \mathsf{P}$.

$\endgroup$
8
  • 1
    $\begingroup$ Maybe I'm being slow here, but how does NP=coNP imply ZPP=RP=coRP=BPP? $\endgroup$ Feb 15, 2014 at 15:39
  • $\begingroup$ @JoshuaGrochow I am stuck at that too. $\endgroup$
    – Tayfun Pay
    Feb 15, 2014 at 16:31
  • $\begingroup$ Thank you, I indeed missed a condition. I corrected the answer. $\endgroup$ Feb 15, 2014 at 18:58
  • $\begingroup$ @AndrasFarago okay! +1 :) $\endgroup$
    – Tayfun Pay
    Feb 15, 2014 at 20:43
  • 2
    $\begingroup$ @user514014 If NP=co-NP, then PH collapses to NP=co=NP. If also NP=RP, then NP=RP=co-RP. As BPP is in PH and contains RP, this means BPP=RP=co-RP. Since ZPP is the intersection of RP and co-RP we get BPP=ZPP. $\endgroup$ Aug 5, 2020 at 14:48
7
$\begingroup$

There are two definitions for counting classes beyond ${\bf \#P}$. One was defined by Valiant and the other one was defined by Toda.

${ \rm \underline {Valiant's-Definition:}}$ For any class $C$, define $\#C =\cup_{A\in C}(\#P)^{A}$, where $({\#P}^A)$ means the functions counting the accepting paths of nondeterministic polynomial-time Turing machines having $A$'s their oracle.

By Valiant's definition we already have ${\bf \#NP} = {\bf \#CoNP}$

${ \rm \underline {Toda's-Definition:}}$ For any class $C$, define $\# .C$ to be the class of functions $f$ such that for some $C-$computable two-argument predicate $R$ and some polynomial $p$, for every string $x$ it holds that: $f(x)=||\{y|p(|x|)=|y|$ and $R(x,y)\}||$.

By Toda's definition we have ${\bf \#.NP} = {\bf \#.CoNP}$ if and only if ${\bf NP} = {\bf CoNP}$.

Then if we also assume that ${\bf P}\not = {\bf NP}$ then we would have ${\bf FP} \not = {\bf \# P}$.

$\endgroup$
3
  • $\begingroup$ It is the counting version of NP. $\endgroup$
    – Tayfun Pay
    Sep 6, 2011 at 1:38
  • $\begingroup$ What does the period refer to in "#.NP"? $\endgroup$ Sep 14, 2011 at 4:30
  • 5
    $\begingroup$ There are two types if counting hierachies defined. One by Valiant in1979 and he uses the notation #P, #NP,#Co-NP... Where #NP=Co-NP. On the other hand Toda defined a different hierarchy. And the notation for that uses dots. And #.NP!=#.Co-NP unless NP=Co-NP $\endgroup$
    – Tayfun Pay
    Sep 14, 2011 at 12:19
2
$\begingroup$

Ker-i Ko Showed that there is an oracle that makes PH collapse at the k-th level. See "Ker-I Ko: Relativized Polynomial Time Hierarchies Having Exactly K Levels. SIAM J. Comput. 18(2): 392-408 (1989)".

$\endgroup$
6
  • $\begingroup$ Can you link us to the paper? $\endgroup$
    – Tayfun Pay
    Jan 26, 2012 at 21:09
  • $\begingroup$ @ BinFu Tks - I thought that PH collapses to the first level... $\endgroup$ Jan 26, 2012 at 23:49
  • 1
    $\begingroup$ For the case k=1, it is the case of this problem. The polynomial time does collapse to NP under the condition NP=coNP. The existence of the oracle for k-th level in Ko's paper means the barrier of any relativized method to deal with PH collapse problem. $\endgroup$
    – Bin Fu
    Jan 27, 2012 at 16:15
  • 1
    $\begingroup$ @BinFu: your remarks don't describe any consequences of PNP = coNP. The question was not how to show a collapse to the first level, or about results which also describe a collapse to the first level, but what would be known as a corollary of a collapse to the first level. I don't see how your answer bears on that at all. $\endgroup$ Jan 28, 2012 at 12:47
  • 1
    $\begingroup$ Every satisfiable Boolean formula has a polynomial time and length proof, which is the truth assignments to make the formula true. The condition NP=coNP makes every unsatisfiable boolean formula has a polynomial time and length proof. If P is not equal to NP, and NP=coNP, then there is no polynomial time algorithm to find the polynomial length proof for a boolean formula for its satisfiability or unsatisfiability. Similarly, we will have similar conclusions for all the problems in NP. $\endgroup$
    – Bin Fu
    Jan 30, 2012 at 14:59

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .