Editing P versus NP problem (section)

==Consequences of solution==
One of the reasons the problem attracts so much attention is the consequences of the possible answers. Either direction of resolution would advance theory enormously, and perhaps have huge practical consequences as well.

===P = NP===
A proof that P&nbsp;=&nbsp;NP could have stunning practical consequences if the proof leads to efficient methods for solving some of the important problems in NP. The potential consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields.

It is also very possible that a proof would ''not'' lead to practical algorithms for NP-complete problems.  The formulation of the problem does not require that the bounding polynomial be small or even specifically known. A [[non-constructive proof]] might show a solution exists without specifying either an algorithm to obtain it or a specific bound. Even if the proof is constructive, showing an explicit bounding polynomial and algorithmic details, if the polynomial is not very low-order the algorithm might not be sufficiently efficient in practice. In this case the initial proof would be mainly of interest to theoreticians, but the knowledge that polynomial time solutions are possible would surely spur research into better (and possibly practical) methods to achieve them.

A solution showing P&nbsp;=&nbsp;NP could upend the field of [[cryptography]], which relies on certain problems being difficult. A constructive and efficient solution<ref group="Note">Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of <math>O(N^2)</math> with a reasonable constant term would be disastrous. On the other hand, a solution that is <math>\Omega(N^4)</math> in almost all cases would not pose an immediate practical danger.</ref> to an NP-complete problem such as [[Boolean satisfiability problem#3-satisfiability|3-SAT]] would break most existing cryptosystems including:
* Existing implementations of [[public-key cryptography]],<ref>See {{cite book |contribution=Hard instance generation for SAT |author1=Horie, S. |author2=Watanabe, O. |title=Algorithms and Computation |pages=22–31 |year=1997 |publisher=Springer |arxiv=cs/9809117 |bibcode=1998cs........9117H |doi=10.1007/3-540-63890-3_4 |series=Lecture Notes in Computer Science |isbn=978-3-540-63890-2 |volume=1350}} for a reduction of factoring to SAT. A 512-bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.</ref> a foundation for many modern security applications such as secure financial transactions over the Internet.
* [[Symmetric cipher]]s such as [[Advanced Encryption Standard|AES]] or [[Triple DES|3DES]],<ref>See, for example, {{cite journal |title=Logical cryptanalysis as a SAT problem |author1=Massacci, F. |author2=Marraro, L. |journal=Journal of Automated Reasoning |volume=24 |issue=1 |pages=165–203 |year=2000 |citeseerx=10.1.1.104.962 |doi=10.1023/A:1006326723002 |s2cid=3114247 }} in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size.</ref> used for the encryption of communications data.
* [[Cryptographic hash function|Cryptographic hashing]], which underlies [[blockchain]] [[cryptocurrency|cryptocurrencies]] such as [[Bitcoin]], and is used to authenticate software updates.  For these applications, finding a pre-image that hashes to a given value must be difficult, ideally taking exponential time. If P&nbsp;=&nbsp;NP, then this can take polynomial time, through reduction to SAT.<ref>{{cite conference
 |title=Inversion attacks on secure hash functions using SAT solvers
 |author1=De, Debapratim |author2=Kumarasubramanian, Abishek |author3=Venkatesan, Ramarathnam
 |book-title=Theory and Applications of Satisfiability Testing&nbsp;– SAT 2007
 |conference=International Conference on Theory and Applications of Satisfiability Testing
 |pages=377–382
 |year=2007
 |publisher=Springer
 |doi=10.1007/978-3-540-72788-0_36
 }}</ref>
These would need modification or replacement with [[information-theoretic security|information-theoretically secure]] solutions that do not assume P&nbsp;≠&nbsp;NP.

There are also enormous benefits that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in [[operations research]] are NP-complete, such as types of [[integer programming]] and the [[travelling salesman problem]]. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in [[protein structure prediction]], are also NP-complete;<ref name="Berger">{{Cite journal |author1-link=Bonnie Berger |last1=Berger |first1=B. |author2-link=F. Thomson Leighton |last2=Leighton |first2=T. |title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete |journal=J. Comput. Biol. |volume=5 |issue=1 |pages=27–40 |year=1998 |pmid=9541869 |doi=10.1089/cmb.1998.5.27 |citeseerx=10.1.1.139.5547 }}</ref> making these problems efficiently solvable could considerably advance life sciences and biotechnology.

These changes could be insignificant compared to the revolution that efficiently solving NP-complete problems would cause in mathematics itself. Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics:<ref>History of this letter and its translation from {{cite web |title=The History and Status of the P versus NP question |first=Michael |last=Sipser |url=http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf |archive-url=https://web.archive.org/web/20140202095503/http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf |archive-date=2014-02-02 |url-status=live}}</ref><ref>{{cite book |chapter=A Brief History of NP-Completeness, 1954–2012 |first=David S. |last=Johnson |date=August 2012 |pages=359–376 |title=Optimization Stories |editor-link=Martin Grötschel |editor-first=M. |editor-last=Grötschel |series=Documenta Mathematica |url=https://www.academia.edu/download/53654761/Groetschel-Gertzen_Petrie_DocMath.pdf |isbn=978-3-936609-58-5 |issn=1431-0643}}</ref>
{{quote|If there really were a machine with φ(''n'') ∼ ''k''⋅''n'' (or even ∼ ''k''⋅''n''<sup>2</sup>), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the [[Entscheidungsproblem]], the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number ''n'' so large that when the machine does not deliver a result, it makes no sense to think more about the problem.}}
Similarly, [[Stephen Cook]] (assuming not only a proof, but a practically efficient algorithm) says:<ref name="Official Problem Description">{{Cite web |last=Cook |first=Stephen |author-link=Stephen Cook |title=The P versus NP Problem |website=[[Clay Mathematics Institute]] |date=April 2000|url=
https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf|archive-url=https://web.archive.org/web/20131216004059/http://www.claymath.org/sites/default/files/pvsnp.pdf |archive-date=2013-12-16 |url-status=live |access-date=18 October 2006}}</ref>
{{quote|...&nbsp;it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the [[Clay Math Institute#Millennium Prize Problems|CMI prize problems]].}}

Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated—for instance, [[Fermat's Last Theorem]] took over three centuries to prove. A method guaranteed to find a proof if a "reasonable" size proof exists, would essentially end this struggle.

[[Donald Knuth]] has stated that he has come to believe that P&nbsp;=&nbsp;NP, but is reserved about the impact of a possible proof:<ref>{{cite book |url=http://www.informit.com/articles/article.aspx?p=2213858&WT.rss_f=Article&WT.rss_a=Twenty%20Questions%20for%20Donald%20Knuth&WT.rss_ev=a |title=Twenty Questions for Donald Knuth |date=20 May 2014 |publisher=[[InformIT (publisher)|InformIT]] |last=Knuth |first=Donald E. |author-link=Donald Knuth |access-date=20 July 2014}}</ref>
{{quote|1= [...] if you imagine a number ''M'' that's finite but incredibly large—like say the number 10↑↑↑↑3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do ''n''<sup>''M''</sup> bitwise or addition or shift operations on ''n'' given bits, and it's really hard to believe that all of those algorithms fail.

My main point, however, is that I don't believe that the equality P&nbsp;=&nbsp;NP will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive.}}
[[File:Complexity classes.svg|thumb|250px|Diagram of complexity classes provided that P&nbsp;[[≠]]&nbsp;NP. The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by [[NP-intermediate|Ladner's theorem]].<ref name="Ladner75">{{cite journal |first=R.E. |last=Ladner  |title=On the structure of polynomial time reducibility |journal=[[Journal of the ACM]] |volume=22 |pages=151–171 See Corollary&nbsp;1.1 |year=1975 |doi=10.1145/321864.321877 |s2cid=14352974 |doi-access=free }}</ref>]]

===P ≠ NP===
A proof of P&nbsp;≠&nbsp;NP would lack the practical computational benefits of a proof that P&nbsp;=&nbsp;NP, but would represent a great advance in computational complexity theory and guide future research. It would demonstrate that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P&nbsp;≠&nbsp;NP, much of this focusing of research has already taken place.<ref>{{Cite journal |title=The Heuristic Problem-Solving Approach |author=L. R. Foulds |journal=[[Journal of the Operational Research Society]] |volume=34 |issue=10 |date=October 1983 |pages=927–934 |jstor=2580891 |doi=10.2307/2580891}}</ref>

P&nbsp;≠&nbsp;NP still leaves open the [[average-case complexity]] of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable. [[Russell Impagliazzo]] has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question.<ref>R. Impagliazzo, [http://cseweb.ucsd.edu/~russell/average.ps "A personal view of average-case complexity"], p.&nbsp;134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995.</ref> These range from "Algorithmica", where P&nbsp;=&nbsp;NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P&nbsp;≠&nbsp;NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P&nbsp;≠&nbsp;NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A [[Princeton University]] workshop in 2009 studied the status of the five worlds.<ref>{{Cite web |url = http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/ |title = Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds" |archive-url = https://web.archive.org/web/20131115034042/http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/ |archive-date = 2013-11-15}}</ref>