0

1

Do you believe P=NP?
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?

flag
8 
 MO is for questions which have the possibility of clear correct answers. This question is the definition of subjective and argumentative. – Noah Snyder Apr 15 2011 at 17:47
1 
 I respect your opinion but disagree. If a question brings to life elucidating answers such as Emil's, how bad can it be? – B. Apr 15 2011 at 18:06
2 
 @Bel: The purpose of MO is quite narrow. Not every good question related to mathematics is suitable for MO. Please, see the FAQs. – quid Apr 15 2011 at 18:16
2 
 This seems to be essentially the same as mathoverflow.net/questions/47954/… so I'm voting to close. – Andreas Blass Apr 15 2011 at 18:20
6 
 Bel, good answers such as that of Emil are not a problem. The problem is the possibility of lengthy arguments, sometimes quite rancorous, that do occur as answers or `comments.' It is hoped to avoid difficulties that plague many other mathematics websites. As a result, a question such as yours, of the type we think of as "department tea" questions, may be thought of as allowing too much latitude for pontification. Now, the angriest discussions tend to be about the topic of closing questions. Consider looking at the `comments' in other recent closed questions. – Will Jagy Apr 15 2011 at 19:10
show 2 more comments

closed as subjective and argumentative by Noah Snyder, Will Jagy, Dan Petersen, Ryan Budney, Tony Huynh Apr 15 2011 at 18:19

2 Answers

17

Contrary to a popular misunderstanding: if P = NP, then the proof of any statement $A$ can be found by an algorithm in time polynomial in the length of the shortest proof of $A$, 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.

link|flag
5 
 A closely related question is mathoverflow.net/questions/57848/… . What I find interesting is that people have strong sentiments that even under NP=P the practices of mathematics will not be very different and we will continue doing mathematics the way it is done today in order to produce elegant illuminating human-comprehensible proofs. I disagree with this view and I do not understand this sentiment. In particular, I disagree with the last sentence of Emil's answer. – Gil Kalai Apr 15 2011 at 20:09
1

"Do you believe P=NP?" - no.

"...Do you agree with that? Does the possibility of P=NP bother you?" - no.

But what I believe does not matter very much...

link|flag

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