principleCritical
If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?
Viewed 0 times
whyeveryoneforbelievesattemptsscepticalproof
Problem
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?
Solution
People are skeptical because:
To be clear, the skepticism is of the proofs, not of the result itself.
- 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.
Context
StackExchange Computer Science Q#82679, answer score: 96
Revisions (0)
No revisions yet.