[Solved]: Why do most scientists believe that P≠NP?

Problem Detail: 

I read that most scientists don't believe that P=NP. It might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some "pretty simple" explanation why to believe one or the other case, for instance why even believe that it can be proved?

Asked By : Dac Saunders

Answered By : Juho

An NP-complete problem can be transformed into another NP-complete problem. There's an abundance of known NP-complete problems, in fact, one could even say that any really interesting problem is NP-complete. So if you know of a way of solving any NP-complete problem $X$ quickly, you can take any other NP-complete problem, transform it into an instance of $X$, and solve that quickly as well.

Several smart researches have spent a lot of time on researching these hard problems. Despite all the efforts and years, we still don't have a polynomial time algorithm for any of the NP-complete problems. We also have conditional results of the form "if you can do this faster/better, then P=NP".

As for proving the claim, we don't perhaps know much for sure. What we do know is that whatever the proof looks like, it can't be of a certain type. So at least if there ever was a proof, it will have to address how it avoids some known difficulties.

For more details, you could first have a look at Sipser's book, and then the Arora-Barak book.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14487