18

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

András Salamon
  • 19,000
  • 3
  • 64
  • 150
Xavier Labouze
  • 1,117
  • 1
  • 9
  • 27
  • 4
    In that case PH still collapses (to the 1st rather than 0th level). – Huck Bennett Sep 05 '11 at 01: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 05 '11 at 03:47
  • 2
    @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 05 '11 at 08: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 05 '11 at 09:03
  • @ArtemKaznatcheev : tks to your understanding comment – Xavier Labouze Sep 05 '11 at 09:36
  • @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 Sep 06 '11 at 00:26
  • How about to delta level? :) – Tayfun Pay Sep 06 '11 at 01:46
  • 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 Sep 06 '11 at 15:48
  • @user834: search for Impagliazzo's worlds. – Kaveh Sep 14 '11 at 10:15
  • @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 Sep 15 '11 at 16:39

4 Answers4

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.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
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}$.

Andras Farago
  • 11,396
  • 37
  • 70
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}$.

Tayfun Pay
  • 2,598
  • 2
  • 18
  • 45
  • It is the counting version of NP. – Tayfun Pay Sep 06 '11 at 01:38
  • What does the period refer to in "#.NP"? – Timothy Sun Sep 14 '11 at 04:30
  • 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 – Tayfun Pay Sep 14 '11 at 12:19
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)".

Bin Fu
  • 674
  • 4
  • 8
  • 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
  • -1. This answer is not really addressing the original question. – Niel de Beaudrap Jan 27 '12 at 13:48
  • 1
    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
  • 1
    @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
  • 1
    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