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?
$\begingroup$
$\endgroup$
3
asked Sep 21, 2013 at 4:09
-
3$\begingroup$ Did you look at P versus NP problem were several arguments are presented? I find Wikipedia's answer to your question quite valuable. $\endgroup$– J.-E. PinSep 21, 2013 at 10:54
-
4$\begingroup$ Several argument for this can be found here : scottaaronson.com/blog/?p=122 $\endgroup$– TpecatteSep 21, 2013 at 13:01
-
1$\begingroup$ @Timot Thank you very much for pointing out this blog. It is actually the last reference given on the wikipedia page but it is really worth to give a direct link to it. Maybe you should post your comment as an answer. $\endgroup$– J.-E. PinSep 21, 2013 at 14:21
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
-
14$\begingroup$ I strongly disagree with your contention that "any really interesting problem is NP-complete". $\endgroup$ Sep 22, 2013 at 5:20
$\begingroup$
$\endgroup$
1
P≠NP seems to be a sort of "computational speed limit" or "no free lunch theorem" or "fundamental bottleneck" of which there are many other similar examples from many branches of science, mathematics, and even physics. the amount of computation required to solve a SAT problem is exponential in all known algorithms, and there are many that have been invented over the years by top researchers. decades of research have gone into solving SAT alone, in fact over ½-century of research eg since the Davis Putnam algorithm which was found and analyzed in ~1960 even a decade before the theory of NP completeness in the early 1970s.
intuitively P≠NP states that no matter how brilliantly creative the algorithm designer is, there are fundamental limits in improving the efficiency of code. in this way it even has parallels to physical laws eg thermodynamics. its can be interpreted as a limit on the amount of information processing that can be done per time by any physical system.
but, no one thinks there is a "pretty simple" reason the theorem is true, at least in the sense of proof structure, because if such a reason existed, it seems like it would be discovered by now. in other words it seems to be true but the reason is "extremely complicated". possibly from a few decades of future research and analysis/simplification after it is proved, it might start to look "simpler" in 20-20 hindsight/retrospect, some proofs esp critical ones go through that somewhat evolutionary process over time.
another angle on this is that modern cryptography is based on the existence of "hard" functions and "trapdoor" type functions in which computation is easy in one way and not the other. in other words researchers are so confident in the belief that P≠NP they've built elaborate cryptographic systems based on the premise.
however, a small minority of researchers "dont rule out" P=NP some of them accomplished experts, eg RJ Lipton.
One of the reasons for these posts is that I believe that much of what we believe as a community about P$\stackrel{?}{=}$NP may be at best guesswork and at worst just plain wrong. Most think that “obviously” P≠NP, yet I am not so sure. I really think that the opposite could just as well hold.
see these nice polls by Gasarch
[1] Gasarch P vs NP poll I, 2002
[2] Gasarch P vs NP poll II, 2012
as for its inherent provability, there is some serious expert debate on that subject. see this ref/survey, and also a famous award-winning paper.
[3] is P≠NP formally independent? Aaronson
[4] Natural proofs Razborov/Rudich
-
1$\begingroup$ "intuitively P≠NP states that [...] there are fundamental limits in improving the efficiency of code." True but note that the time hierarchy theorem already says that, says it in more detail than $\mathrm{P\neq NP}$ and says it in a way that's still true even if it turns out that $\mathrm{P=NP}$. $\endgroup$ Dec 23, 2014 at 8:54
$\begingroup$
$\endgroup$
I think that people always believe the conjecture that has "more quantifiers." We always conjecture that "there is no such number as" rather than "there is a number" or that "there are infinitely many such numbers" rather than "there are no more numbers larger than this." One reason should be that we feel that if there was such a number/bound, then we could find it/guess it.
With P=NP, if you thought that they were equal, then you should think that there is an algorithm for SAT, again a constructive thing, which if we cannot show that exits, we conjecture that it does not. At least after a lot of smart people have worked on it and could not find it.
Note that P=NP is different from number theory conjectures, which are based on some empirical evidence, like assuming that primes behave like random numbers. Here there is no supporting assumption, except that until now no one could find an algorithm. I suppose this makes the conjecture "less likely" but of course there can be no formal way of assigning probabilities to mathematical statements.
But probably you are better off reading the opinions of experts, see here: http://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP
