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$ Commented 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
    Commented 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$ Commented 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$ Commented Sep 5, 2011 at 9:03
  • $\begingroup$ @ArtemKaznatcheev : tks to your understanding comment $\endgroup$ Commented 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
    Commented 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$ Commented Feb 16, 2014 at 15:16
  • $\begingroup$ To expand on that last paragraph see "The Relative Efficiency of Propositional Proof Systems" $\endgroup$
    – AHusain
    Commented 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$ Commented Feb 15, 2014 at 15:39
  • $\begingroup$ @JoshuaGrochow I am stuck at that too. $\endgroup$
    – Tayfun Pay
    Commented Feb 15, 2014 at 16:31
  • $\begingroup$ Thank you, I indeed missed a condition. I corrected the answer. $\endgroup$ Commented Feb 15, 2014 at 18:58
  • $\begingroup$ @AndrasFarago okay! +1 :) $\endgroup$
    – Tayfun Pay
    Commented 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$ Commented 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
    Commented Sep 6, 2011 at 1:38
  • $\begingroup$ What does the period refer to in "#.NP"? $\endgroup$ Commented 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
    Commented 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
    Commented Jan 26, 2012 at 21:09
  • $\begingroup$ @ BinFu Tks - I thought that PH collapses to the first level... $\endgroup$ Commented 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
    Commented 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$ Commented 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
    Commented Jan 30, 2012 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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