11
$\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$
  • 3
    $\begingroup$ In that case PH still collapses (to the 1st rather than 0th level). $\endgroup$ – Huck Bennett Sep 5 '11 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 '11 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$ – Artem Kaznatcheev Sep 5 '11 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$ – Giorgio Camerani Sep 5 '11 at 9:03
  • $\begingroup$ @ArtemKaznatcheev : tks to your understanding comment $\endgroup$ – Xavier Labouze Sep 5 '11 at 9:36
16
$\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$
  • $\begingroup$ I like this answer! +1 $\endgroup$ – Tayfun Pay Feb 15 '14 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$ – Xavier Labouze Feb 16 '14 at 15:16
11
$\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$
  • 1
    $\begingroup$ Maybe I'm being slow here, but how does NP=coNP imply ZPP=RP=coRP=BPP? $\endgroup$ – Joshua Grochow Feb 15 '14 at 15:39
  • $\begingroup$ @JoshuaGrochow I am stuck at that too. $\endgroup$ – Tayfun Pay Feb 15 '14 at 16:31
  • $\begingroup$ Thank you, I indeed missed a condition. I corrected the answer. $\endgroup$ – Andras Farago Feb 15 '14 at 18:58
  • $\begingroup$ @AndrasFarago okay! +1 :) $\endgroup$ – Tayfun Pay Feb 15 '14 at 20:43
  • $\begingroup$ @AndrasFarago Tks for your answer ! $\endgroup$ – Xavier Labouze Feb 16 '14 at 13:49
6
$\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$
  • $\begingroup$ It is the counting version of NP. $\endgroup$ – Tayfun Pay Sep 6 '11 at 1:38
  • $\begingroup$ What does the period refer to in "#.NP"? $\endgroup$ – Timothy Sun Sep 14 '11 at 4:30
  • 4
    $\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 '11 at 12:19
1
$\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$
  • $\begingroup$ Can you link us to the paper? $\endgroup$ – Tayfun Pay Jan 26 '12 at 21:09
  • $\begingroup$ @ BinFu Tks - I thought that PH collapses to the first level... $\endgroup$ – Xavier Labouze Jan 26 '12 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 '12 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$ – Niel de Beaudrap Jan 28 '12 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 '12 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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