# Consequences of $NP=coNP$ and $P\ne NP$?

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

• In that case PH still collapses (to the 1st rather than 0th level). – Huck Bennett Sep 5 '11 at 1:15
• 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 Sep 5 '11 at 3:47
• @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 Sep 5 '11 at 8:08
• @Xavier: Why do you say "...and we are in trouble". P = NP, and the consequent PH collapse, would be just fantastic ;-) – Giorgio Camerani Sep 5 '11 at 9:03
• @ArtemKaznatcheev : tks to your understanding comment – Xavier Labouze Sep 5 '11 at 9:36

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.

• I like this answer! +1 – Tayfun Pay Feb 15 '14 at 17:04
• 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 Feb 16 '14 at 15:16

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

• Maybe I'm being slow here, but how does NP=coNP imply ZPP=RP=coRP=BPP? – Joshua Grochow Feb 15 '14 at 15:39
• @JoshuaGrochow I am stuck at that too. – Tayfun Pay Feb 15 '14 at 16:31
• Thank you, I indeed missed a condition. I corrected the answer. – Andras Farago Feb 15 '14 at 18:58
• @AndrasFarago okay! +1 :) – Tayfun Pay Feb 15 '14 at 20:43
• @AndrasFarago Tks for your answer ! – Xavier Labouze Feb 16 '14 at 13:49

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

• It is the counting version of NP. – Tayfun Pay Sep 6 '11 at 1:38
• What does the period refer to in "#.NP"? – Timothy Sun Sep 14 '11 at 4:30
• 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 Sep 14 '11 at 12:19

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

• Can you link us to the paper? – Tayfun Pay Jan 26 '12 at 21:09
• @ BinFu Tks - I thought that PH collapses to the first level... – Xavier Labouze Jan 26 '12 at 23:49
• 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 Jan 27 '12 at 16:15
• @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. – Niel de Beaudrap Jan 28 '12 at 12:47
• 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 Jan 30 '12 at 14:59