Editing P versus NP problem (section)

===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>