54
$\begingroup$

Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, then you should also believe that sound arguments for $P\ne NP$ are lacking. Or are there good arguments for $P\ne NP$ being unlikely, in a similar vein to say, the Riemann hypothesis holding for large numbers, or the very high lower bounds on the number of existing primes with a small distance apart viz. the Twin Prime conjecture?

$\endgroup$
  • 61
    $\begingroup$ Because wishful thinking makes no proof. And because it's not everybody. And because "believe" is not enough for most mathematically thinking people. $\endgroup$ – Raphael Oct 19 '17 at 5:32
  • 26
    $\begingroup$ "why is everyone sceptical of proof attempts" is something quite different from "many believe it very unlikely that this will ever be proven". $\endgroup$ – Tom van der Zanden Oct 19 '17 at 9:06
  • 95
    $\begingroup$ I believe in the existence of the president of Nigeria and that he sometimes faces problems related to moving currency around. Yet I am skeptical of the emails I receive that claim to be asking for my help with these problems. $\endgroup$ – Gilles Oct 19 '17 at 11:41
  • 3
    $\begingroup$ at this point the problem has been open almost ½ century and theres an unclaimed $1M award for over 1½ decade (Claymath). the problem is therefore likely roughly as and/or at least as hard as epic problems like those you mention (Riemann/ Twin primes). Riemann is unsolved for ~1½ century and twin primes is still unsolved after ~2millenia. in other words the general consensus/ conventional wisdom is it "seems to be true" but for "reasons that are beyond current human comprehension/ existing mathematical techniques/ knowledge". most scientists however believe it will eventually be solved... $\endgroup$ – vzn Oct 19 '17 at 17:19
  • 3
    $\begingroup$ Seems like everyone has focused on justifying the good reasons for being skeptical of new attempted proofs... but no one has really addressed what I thought was OPs core question: why/how are we so confident that something that seems unprovable is still likely true? as a complete layman idiot it seems to me analogous to being harder to prove a thing doesn't exist than a thing does exist (if you have the thing then the latter is easy, but for the former you're never sure if it really doesn't exist or you just didn't find it yet) $\endgroup$ – Anentropic Oct 20 '17 at 12:59
94
$\begingroup$

People are skeptical because:

  • No proof has come from an expert without having been rescinded shortly thereafter
  • So much effort has been put into finding a proof, with no success, that it's assumed one will be either substantially complicated, or invent new mathematics for the proof
  • The "proofs" that arise frequently fail to address hurdles which are known to exist. For example, many claim that 3SAT is not in P, while providing an argument that also applies to 2SAT.

To be clear, the skepticism is of the proofs, not of the result itself.

$\endgroup$
  • 16
    $\begingroup$ An important point is that broad classes of proof techniques have been shown not to be sufficient. See Wikipedia edit: also mentioned in Evil's answer $\endgroup$ – JollyJoker Oct 19 '17 at 11:04
  • 4
    $\begingroup$ Another reason I find important is the severity of the situation if one gets the answer wrong. If one assumes P≠NP, and that turns out to be false, there's literally billions of dollars worth of infrastructure and transactions which are primarily protected by the presumed NP nature of an attack on their cryptography. $\endgroup$ – Cort Ammon Oct 19 '17 at 21:59
  • 14
    $\begingroup$ @CortAmmon But discovering deterministic $\Theta(n^{100})$ algorithms to those problems probably wouldn't make any practical difference. $\endgroup$ – David Richerby Oct 20 '17 at 15:04
  • $\begingroup$ @DavidRicherby - on the other hand, at least with breaking cryptographic algorithms complexity often comes substantially down over time. $\endgroup$ – TLW Oct 24 '17 at 2:29
  • $\begingroup$ @TLW Sorry, I was imprecise. I meant that it would make little difference to cryptography if we discovered that problems in NP have polynomial-time algorithms but that every such algorithm had running time $\Omega(n^{100})$. In that case, there's no scope for improvement. $\endgroup$ – David Richerby Oct 24 '17 at 8:23
44
$\begingroup$

Beliefs are orthogonal to proofs. Belief may direct attempted solutions by researchers or rather their main interest but this does not prevent them from checking a proof anyway.

The problem with $P \ne NP$ that many standard ways of attempting a proof are already excluded as not sufficient to infer anything, see here for further details.

There is no inconsistency in gathered poll of suspicions and educated conjectures. Also the belief that something will not be proven is not insightful in any way, without a proof of unprovability.

The years of attempts, claims, and discarded methods render people skeptical.

Please look at the prior papers that tried to contribute something towards the resolution.

"Extraordinary claims require extraordinary evidence."

This quite accurately characterizes the skepticism.

$\endgroup$
  • 7
    $\begingroup$ Well, not orthogonal. Clearly being proved true is correlated with being believed to be true. $\endgroup$ – Acccumulation Oct 20 '17 at 3:25
  • 2
    $\begingroup$ Doesn't your highlighted quote actually talk to what the original question is asking? I.e: If the statement P≠NP is so widely believed and accepted then why is it an extraordinary claim, shouldn't it be an ordinary claim? I guess it's as you say, the extraordinary claim isn't that P≠NP but that a proof has been found. And that would be extraordinary just based on the history of attempted proofs. Not sure what my point is, except for the fact that your emphasis on that quote was interesting. :) $\endgroup$ – Jack Casey Oct 20 '17 at 4:44
  • 3
    $\begingroup$ If you're using "orthogonal" to mean something other than "uncorrelated", then I think you're using it in a nonstandard way. $\endgroup$ – Acccumulation Oct 20 '17 at 13:40
  • 1
    $\begingroup$ I use the word "orthogonal" in the most standard and cs/math/dsp compilant way and I do not agree with correlation, given standard MO, and even gave conterexample. It is not correlated from scientific point of view, but it is from behavioral heuristics, which should not be mixed. $\endgroup$ – Evil Oct 20 '17 at 18:09
  • 1
    $\begingroup$ @JackCasey, the claim is extraordinary because it hasn't been proven, compared to thousands of other proven claims. It doesn't matter that everyone "believes" so. $\endgroup$ – Arturo Torres Sánchez Oct 23 '17 at 13:59
22
$\begingroup$

A few reasons, some generic and some specific.

The generic reason is that this is a long-known famous problem which many smart people have tried to solve, and many smart people have gotten wrong. The odds that any one new proof is valid is extremely low based off this history.

In this specific case, there has been research on what proofs don't work. It has been shown that basically all known proof techniques for proving things in computer science cannot prove P!=NP.

Wikipedia covers this and points out how "Relativizing proofs" (proofs that work regardless of what oracles your TM has access to), "Natural proofs" (involving circuit lower bounds), and "arithmetization" are all either insufficient to distinguish P and NP (show them equal or different), or any such proof would be a ridiculously more powerful result.

In short, not only have many smart people been working at this a long time and failed, along the way they have proven entire families of proofs cannot be used to solve this problem. So when someone comes up with P!=NP, there is natural skepticism, followed by noticing that one of the many proofs about such proofs is violated, and then there is no longer a need to check the rest of the result.

$\endgroup$
  • $\begingroup$ I wonder if it is actually true that many smart people tried to prove P ≠ NP, or if they focused on something achievable, like showing that certain known proof techniques don't work. $\endgroup$ – gnasher729 Oct 19 '17 at 23:37
  • 3
    $\begingroup$ @gnasher Read wikipedia. Those "this technique cannot work" proofs flowed out of attempts to use those techniques to prove P?=NP. Anyone comes up with a non-Relitivising proof of anything in CS that does not fall under the other ruled out proof techniques, you bet people will try it. $\endgroup$ – Yakk Oct 20 '17 at 0:08
  • $\begingroup$ The ACC0 lower bound from Ryan Williams seemingly evades all known barriers (if they exist for ACC0 circuits). $\endgroup$ – Lwins Jun 30 at 7:33
7
$\begingroup$

People don't believe any "proofs" because of the perceived difficulty.

Let's say we meet aliens who are better at maths than humans. Their average school child is about as good at maths as our greatest mathematicians. Not a smart school child, but an average school child.

They have proved the Riemann Hypothesis, the Twin Prime Theorem and the first Hardy-Littlewood Conjecture, and Goldbach's Hypothesis. What do they think about proving that the Travelling Salesman problem can be solved in polynomial time? They will find it unlikely that anyone could solve this. What do they think about proving that the Travelling Salesman problem cannot be solved in polynomial time? I think they will find it even less likely that someone could find a proof.

That's just my opinion, but if someone says they have a proof for P = NP or P ≠ NP, I won't believe it.

PS. The Riemann Hypothesis is open for a longer time because it is a classical mathematical problem that made sense to mathematicians 100 years ago. P ≠ NP is computer science, something a lot newer, and AFAIK the whole notion of NP comes from the 1970's only. There has been progress on the Riemann Hypothesis (we can't prove "all zeroes yada yada" but at least "a large portion of all zeroes yada yada"), unlike P ≠ NP. It's one-dimensional. It's about the zeroes of one single function. P ≠ NP is about all possible algorithms to solve a problem.

$\endgroup$
  • 7
    $\begingroup$ Why do you think resolving P vs NP is more difficult than the Riemann Hypothesis, say? The latter has been open for much longer. $\endgroup$ – Yuval Filmus Oct 19 '17 at 22:43
  • 4
    $\begingroup$ I don't that speculating at what aliens who are smarter than us might possibly hold as nonfactual opinions is useful. $\endgroup$ – Matthew Read Oct 23 '17 at 8:39
  • 1
    $\begingroup$ There is no correlation between difficulty and age of mathematical problems. There is not a unique solution to a mathematical problem. Difficulty is dependent upon perspective. There may be simple solutions to P = NP and there may be complex ones as well, same with the Riemann Hypothesis and any other conjecture. Finally, to say that RH is about the zeroes of one function and therefore not so hard is not valid. Many hard mathematical problems can be rephrased as about the zeros of a function. $\endgroup$ – Glen Wheeler Oct 24 '17 at 6:11
  • 1
    $\begingroup$ @GlenWheeler How do you define difficulty without invoking how hard people work to solve it which necessarily invokes how long the problem has been available? $\endgroup$ – djechlin Apr 25 at 20:27
  • $\begingroup$ Difficulty is a problematic concept. Instead of using such improperly defined language, instead talk about what you actually mean: e.g. that it has been around for X years, Y of which are as one of the famous "million dollar problems". This is already an indication of what you want to conclude, so the detour through this concept of "difficulty" is completely unnecessary. $\endgroup$ – Glen Wheeler Apr 27 at 1:23
7
$\begingroup$

The reason people are skeptical of proof attempts of P!=NP is the same reason that people are skeptical of proofs of any famous conjecture: false proofs are published every few months and shot down. Meanwhile, correct proofs of famous conjectures seem to have little trouble getting attention, in spite of this (see, for example, the Poincare conjecture or Fermat's Last Theorem), but these proofs often rely on deep knowledge of large-scale efforts by groups of mathematicians (such as Hamilton's Ricci flow for the poincare conjecture or the Taniyama–Shimura–Weil conjecture for Fermat's Last Theorem) even if the final steps were done by a single theorist.

P vs NP is a particularly thorny problem because all the "obvious" methods have not only failed to yield a proof, but been proven to be useless with strong theorems. First time would-be provers are very likely think they have stumbled on a proof but instead have fallen into one of these well-known traps. Remarkably, showing that a number of ways of proving P != NP cannot work are the main advances in the field. It's somewhat outrageous that we cannot even show that 3Sat is not decidable linear time, let alone outside of polynomial time!

I would argue that very few people believe it won't be proven ever however. Indeed, the statement P != NP is a such a basic roadblock in our understanding of computational complexity that it's hard not to think that it's true for a simple and elegant reason.

However, if one wants to be cynical, P != NP is equivalent to the statement that just because a proof is easy (i.e. short) doesn't mean that it's not very hard to find the proof (i.e. takes super-polynomial search time). Indeed most theories believe that there is no sub-exponential time algorithm for finding proofs suggesting that, given any one method of finding proofs (i.e. a mathematician thinking or a computer search), there are many theorems with simple short proofs which are extremely difficult to find (potentially millennia of search time). Whether P != NP is such a theorem is not known of course!

That said, someone could publish the proof tomorrow.

$\endgroup$
4
$\begingroup$

Because you might think it is undecidable, and maybe even undecidable whether it is undecidable. Many mathematical theorems are that way.

$\endgroup$
  • 11
    $\begingroup$ Discussing the decidability of P vs NP is a category error. Decidability is a property of computational problems; P vs NP isn't a computational problem: it's something that's either true or false (or possibly unprovable). The closest analogy is that "Is P=NP?" is a single instance of some other problem. $\endgroup$ – David Richerby Oct 19 '17 at 19:23
  • 2
    $\begingroup$ Also, {"Is P = NP?"} is trivially decidable, as has been discussed before on the site. $\endgroup$ – Raphael Oct 20 '17 at 7:44
  • 5
    $\begingroup$ You guys are a little quick in downvoting imho. My guess id that he is referring to the fact that the hypothesis could be independent of e.g. ZFC which sometimes is called undecidable as well (en.wikipedia.org/wiki/Independence_(mathematical_logic)). $\endgroup$ – D.F.F Oct 20 '17 at 21:42
  • 4
    $\begingroup$ @David he explicitly sets the context to "mathematical theorems". In that context one of the two possible interpretations of the term is nonsensical, it seems natural to me to assume he was referring to the other interpretation. $\endgroup$ – D.F.F Oct 22 '17 at 17:33
  • 3
    $\begingroup$ @D.F.F, I suspect you're missing the point. Many computer scientists do tend to understand the concept of "independence". They also understand the word "independence". The problem comes when someone uses the word "undecidable" to mean "independent", when talking to a computer scientist -- among computer scientists, by default "undecidable" will be taken to mean "Turing-undecidable" (like the halting problem", not "independent". This isn't because computer scientists have never heard of the concept of independence; it's because we have a standard meaning for the term "undecidable". $\endgroup$ – D.W. Oct 23 '17 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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