https://www.scottaaronson.com/papers/pnp.pdf

To summarize, P ? = NP is just the tip of an iceberg; there seems to be an extremely rich structure both below and above the NP-complete problems. Until we can prove P̸ = NP, however, most of that structure will remain conjectural. 3 Beliefs About P ? = NP Just as Hilbert’s question turned out to have a negative answer, so too in this case, most computer scientists conjecture that P̸ = NP: that there exist rapidly checkable problems that aren’t rapidly solvable, and for which brute-force search is close to the best we can do. This is not a unanimous opinion. At least one famous computer scientist, Donald Knuth [155], has professed a belief that P = NP, while another, Richard Lipton [175], professes agnosticism. Also, in a poll of mathematicians and theoretical computer scientists conducted by William Gasarch [105] in 2002, there were 61 respondents who said P̸ = NP, but also 9 who said P = NP. (In a followup poll that Gasarch [106] conducted in 2012, there were 126 respondents who said P̸ = NP, and again 9 who said P = NP.) Admittedly, it can be hard to tell whether declarations that P = NP are meant seriously, or are merely attempts to be contrarian. However, we can surely agree with Knuth and Lipton that we’re far from understanding the limits of efficient computation, and that there are further surprises in store. In this section, I’d like to explain why, despite our limited understanding, many of us feel roughly as confident about P̸ = NP as we do about (say) the Riemann Hypothesis, or other conjectures in math—not to mention empirical sciences—that most experts believe without proof.20 The first point is that, when we ask whether P = NP, we’re not asking whether heuristic optimization methods (such as Sat-solvers) can sometimes do well in practice, or whether there are sometimes clever ways to avoid exponential search. If you believe, for example, that there’s any cryptographic one-way function—that is, any transformation of inputs x → f (x) that’s easy to compute but hard to invert (see Section 5.3.1)—then that’s enough for P̸ = NP. Such an f need not have any “nice” mathematical structure: it could simply be, say, the evolution function of some arbitrary cellular automaton, or a scrambling operation applied over and over 1000 times, to the point where all known cryptanalytic methods can do no better than to scratch the surface. Sometimes amateurs become convinced that they can prove P = NP because of insight into the structure of a particular NP-complete problem, such as 3Sat or SubsetSum. However, this is a bit like thinking that one can solve a math problem because the problem is written in German rather than French. In other words, it fails to grapple with the central insight of NP-completeness: that for the purposes of P ? = NP, all these problems are just re-encodings of one another. It’s sometimes claimed that, when we consider P ? = NP, there’s a “symmetry of ignorance”: yes, we have no idea how to solve NP-complete problems in polynomial time, but we also have no idea how to prove that impossible, and therefore anyone’s free to believe whatever they like. In my opinion, what breaks the symmetry is the immense, well-known difficulty of proving lower bounds. Simply put: even if we suppose P̸ = NP, I don’t believe there’s any great mystery about why a proof has remained elusive. A rigorous impossibility proof is often a tall order, and many times in history—e.g., with Fermat’s Last Theorem, the Kepler Conjecture, or the problem of squaring 20I like to joke that, if computer scientists had been physicists, we’d simply have declared P̸ = NP to be an observed law of Nature, analogous to the laws of thermodynamics. A Nobel Prize would even be given for the discovery of that law. (And in the unlikely event that someone later proved P = NP, a second Nobel Prize would be awarded for the law’s overthrow.) 24