Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

closed as not constructive by Noah Snyder, Will Jagy, Dan Petersen, Ryan Budney, Tony Huynh Apr 15 '11 at 18:19

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

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 '11 at 17:47
2  
I respect your opinion but disagree. If a question brings to life elucidating answers such as Emil's, how bad can it be? –  user14312 Apr 15 '11 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 '11 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 '11 at 18:20
7  
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 '11 at 19:10
show 2 more comments

2 Answers 2

up vote 26 down vote accepted

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.

share|improve this answer
7  
A closely related question is mathoverflow.net/questions/57848/p-vs-np-resistant-problems/… . 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 '11 at 20:09
add comment

"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...

share|improve this answer
add comment

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