<p>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?")</p>

<p>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 <em>any propositional tautology</em>. </p>

<p>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 <em>every</em> tautology has a polynomially short proof - but rather that there is some <em>other</em> reason that we are unable to find those proofs efficiently.</p>

CC BY-SA 3.0
2014-02-15T17:04:39.450Z
I like this answer! +1
Tayfun Pay
CC BY-SA 3.0
2014-02-16T15:16:07.657Z
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 ?
Xavier Labouze
CC BY-SA 4.0
2021-03-12T03:27:47.980Z
To expand on that last paragraph see "The Relative Efficiency of Propositional Proof Systems"
AHusain
CC BY-SA 3.0
2014-02-15T00:04:55.093Z
2014-02-15T00:04:55.093Z
Joshua Grochow
<p>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.</p>

<p>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}$. </p>

<p>The above reasoning shows the interesting effect that the $\mathsf{NP}=co\mathsf{NP}$ hypothesis, despite being a collapse, actually amplifies the <em> separating </em> 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}$. </p>

CC BY-SA 3.0
2014-02-15T15:39:11.060Z
Maybe I'm being slow here, but how does NP=coNP imply ZPP=RP=coRP=BPP?
Joshua Grochow
CC BY-SA 3.0
2014-02-15T16:31:31.217Z
@JoshuaGrochow I am stuck at that too.
Tayfun Pay
CC BY-SA 3.0
2014-02-15T18:58:20.500Z
Thank you, I indeed missed a condition. I corrected the answer.
Andras Farago
CC BY-SA 3.0
2014-02-15T20:43:06.330Z
@AndrasFarago okay! +1 :)
Tayfun Pay
CC BY-SA 3.0
2014-02-16T13:49:33.710Z
@AndrasFarago Tks for your answer !
Xavier Labouze
CC BY-SA 4.0
2020-08-05T08:03:09.610Z
Even if NP = RP and NP = co-NP, why does this imply that ZPP = BPP? Couldn't we just have ZPP = RP = co-RP = NP = co-NP strictly contained in BPP?
user514014
CC BY-SA 4.0
2020-08-05T14:48:33.047Z
@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.
Andras Farago
CC BY-SA 4.0
2020-08-05T17:00:26.507Z
Thank you! That clears it up
user514014
CC BY-SA 3.0
2014-02-15T01:15:45.677Z
2014-02-15T18:57:39.980Z
2014-02-15T18:57:39.980Z
Andras Farago
<p>There are two definitions for counting classes beyond ${\bf \#P}$. One was defined by Valiant and the other one was defined by Toda. </p>

<p>${ \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. </p>

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

<p>${ \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)\}||$.</p>

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

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

CC BY-SA 3.0
2011-09-06T01:38:39.120Z
It is the counting version of NP.
Tayfun Pay
CC BY-SA 3.0
2011-09-14T04:30:34.863Z
What does the period refer to in "#.NP"?
Timothy Sun
CC BY-SA 3.0
2011-09-14T12:19:25.343Z
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
Tayfun Pay
CC BY-SA 3.0
2011-09-05T15:58:32.240Z
2014-02-15T16:27:07.223Z
2014-02-15T16:27:07.223Z
Tayfun Pay
<p>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)". </p>

CC BY-SA 3.0
2012-01-26T21:09:41.137Z
Can you link us to the paper?
Tayfun Pay
CC BY-SA 3.0
2012-01-26T23:49:54.650Z
@ BinFu Tks - I thought that PH collapses to the first level...
Xavier Labouze
CC BY-SA 3.0
2012-01-27T13:48:18.693Z
-1. This answer is not really addressing the original question.
Niel de Beaudrap
CC BY-SA 3.0
2012-01-27T16:15:29.340Z
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.
Bin Fu
CC BY-SA 3.0
2012-01-28T12:47:04.017Z
@BinFu: your remarks don't describe any consequences of **P** ≠ **NP** = **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.
Niel de Beaudrap
CC BY-SA 3.0
2012-01-30T14:59:41.017Z
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.
Bin Fu
CC BY-SA 3.0
2012-01-26T15:01:23.663Z
2012-01-26T15:01:23.663Z
Bin Fu
<p>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 ?)</p>

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

CC BY-SA 3.0
2011-09-05T01:15:10.890Z
In that case PH still collapses (to the 1st rather than 0th level).
Huck Bennett
CC BY-SA 3.0
2011-09-05T03:47:03.407Z
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).
Kaveh
CC BY-SA 3.0
2011-09-05T08:08:15.297Z
@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?
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-05T09:03:32.973Z
@Xavier: Why do you say _"...and we are in trouble"_. P = NP, and the consequent PH collapse, would be just fantastic ;-)
Giorgio Camerani
CC BY-SA 3.0
2011-09-05T09:36:42.690Z
@ArtemKaznatcheev : tks to your understanding comment
Xavier Labouze
CC BY-SA 3.0
2011-09-06T00:26:02.723Z
@Kaveh : The part "we are in trouble" of the first sentence is not important at all, and can be deleted without changing the question.
Xavier Labouze
CC BY-SA 3.0
2011-09-06T01:46:45.097Z
How about to delta level? :)
Tayfun Pay
CC BY-SA 3.0
2011-09-06T15:48:18.497Z
I would be very interested in seeing a kind of overview of what happens should coNP = NP and some references discussing the same.  For example, if coNP = NP then doesn't that say something about the existence of one way hashes/cryptographic functions and thus the ability to use 'natural' proofs to prove P != NP?  Does this mean public key cryptography breaks under coNP = NP?  I've often wondered about this scenario but have not found any good references (though, to be fair, I haven't looked all that hard).
user834
CC BY-SA 3.0
2011-09-14T10:15:08.003Z
@user834: search for Impagliazzo's worlds.
Kaveh
CC BY-SA 3.0
2011-09-15T16:39:27.680Z
@Kaveh, So are you saying that coNP = NP is equivalent to the Pessiland in Impagliazzo's worlds (I did not see an explicit statement of such but I've only skimmed)?  Also, consider making this an answer as it's relevant to the question and we can refer to it if and when others ask similar questions.
user834
<cc.complexity-theory><complexity-classes><conditional-results><polynomial-hierarchy>
Consequences of $NP=coNP$ and $P\ne NP$?
Xavier Labouze
# Consequences of $NP=coNP$ and $P\ne NP$?

(Asked by: username_0 on 2011-09-05)

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

**Tags:** cc.complexity-theory, complexity-classes, conditional-results, polynomial-hierarchy
> **Comments:**
> **username_1**: In that case PH still collapses (to the 1st rather than 0th level).  
> **username_2**: 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).  
> **username_3**: @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?  
> **username_4**: @Xavier: Why do you say _"...and we are in trouble"_. P = NP, and the consequent PH collapse, would be just fantastic ;-)  
> **username_0**: @ArtemKaznatcheev : tks to your understanding comment  
> **username_0**: @Kaveh : The part "we are in trouble" of the first sentence is not important at all, and can be deleted without changing the question.  
> **username_5**: How about to delta level? :)  
> **username_6**: I would be very interested in seeing a kind of overview of what happens should coNP = NP and some references discussing the same.  For example, if coNP = NP then doesn't that say something about the existence of one way hashes/cryptographic functions and thus the ability to use 'natural' proofs to prove P != NP?  Does this mean public key cryptography breaks under coNP = NP?  I've often wondered about this scenario but have not found any good references (though, to be fair, I haven't looked all that hard).  
> **username_2**: @user834: search for Impagliazzo's worlds.  
> **username_6**: @Kaveh, So are you saying that coNP = NP is equivalent to the Pessiland in Impagliazzo's worlds (I did not see an explicit statement of such but I've only skimmed)?  Also, consider making this an answer as it's relevant to the question and we can refer to it if and when others ask similar questions.  

---

## 4 answers

### Answer by username_7 on 2014-02-15. Score: 20

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.

> **Comments:**
> **username_5**: I like this answer! +1  
> **username_0**: 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 ?  
> **username_8**: To expand on that last paragraph see "The Relative Efficiency of Propositional Proof Systems"  

---

### Answer by username_9 on 2014-02-15. Score: 13

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

> **Comments:**
> **username_7**: Maybe I'm being slow here, but how does NP=coNP imply ZPP=RP=coRP=BPP?  
> **username_5**: @JoshuaGrochow I am stuck at that too.  
> **username_9**: Thank you, I indeed missed a condition. I corrected the answer.  
> **username_5**: @AndrasFarago okay! +1 :)  
> **username_0**: @AndrasFarago Tks for your answer !  
> **username_10**: Even if NP = RP and NP = co-NP, why does this imply that ZPP = BPP? Couldn't we just have ZPP = RP = co-RP = NP = co-NP strictly contained in BPP?  
> **username_9**: @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.  
> **username_10**: Thank you! That clears it up  

---

### Answer by username_5 on 2011-09-05. Score: 7

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

> **Comments:**
> **username_5**: It is the counting version of NP.  
> **username_11**: What does the period refer to in "#.NP"?  
> **username_5**: 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  

---

### Answer by username_12 on 2012-01-26. Score: 2

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

> **Comments:**
> **username_5**: Can you link us to the paper?  
> **username_0**: @ BinFu Tks - I thought that PH collapses to the first level...  
> **username_13**: -1. This answer is not really addressing the original question.  
> **username_12**: 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.  
> **username_13**: @BinFu: your remarks don't describe any consequences of **P** ≠ **NP** = **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.  
> **username_12**: 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.  

---

