Do you believe P=NP? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-24T19:58:55Z http://mathoverflow.net/feeds/question/61840 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61840/do-you-believe-pnp Do you believe P=NP? B. 2011-04-15T17:34:20Z 2011-04-15T17:47:10Z <p>Do you believe P=NP?<br> I've seen some mathematicians say that if P=NP their work would be worthless and restricted to enunciating theorems. They seem to believe that there exist an almost philosophical impediment to P=NP. Do you agree with that? Does the possibility of P=NP bother you?</p> http://mathoverflow.net/questions/61840/do-you-believe-pnp/61841#61841 Answer by kakaz for Do you believe P=NP? kakaz 2011-04-15T17:40:49Z 2011-04-15T17:40:49Z <p>"Do you believe P=NP?" - no.</p> <p>"...Do you agree with that? Does the possibility of P=NP bother you?" - no.</p> <p>But what I believe does not matter very much...</p> http://mathoverflow.net/questions/61840/do-you-believe-pnp/61845#61845 Answer by Emil Jeřábek for Do you believe P=NP? Emil Jeřábek 2011-04-15T17:47:10Z 2011-04-15T17:47:10Z <p>Contrary to a popular misunderstanding: if P = NP, then the proof of any statement \$A\$ can be found by an algorithm in time polynomial <em>in the length of the shortest proof of \$A\$</em>, not in the length of \$A\$ itself. Moreover, the exponent of the polynomial could easily be so large as to make this algorithm practically worthless. But most importantly: the shortest, machine-generated, proof of some theorem is highly unlikely to be the most elegant, illuminating, or just human-comprehensible, proof. Thus this idea that under P = NP, mathematics would be reduced to “enunciating theorems”, is completely misguided.</p>