Complexity Theory Codexery

P versus NP problem

A major unsolved problem in theoretical computer science.

Last updated

P is the class of problems solvable in polynomial time, while NP is the class of problems whose answers can be verified in polynomial time.[1] If a problem's answer can be checked quickly, the P versus NP question asks whether that answer can also be found quickly, where "quickly" means in polynomial time.[1]

Quick Facts

Field
Theoretical computer science, computational complexity theory
Related classes
P (polynomial time solvable), NP (nondeterministic polynomial time verifiable)

Facts from the source article.

Key facts and history

Kurt Gödel asked in a 1956 letter whether theorem-proving could be solved in quadratic or linear time.[2] The precise statement of the problem was introduced in 1971 by Stephen Cook and independently by Leonid Levin in 1973.[3] The first natural problem proven to be NP-complete was the Boolean satisfiability problem, known as SAT.[4] The class NP includes problems whose positive solutions are verifiable in polynomial time given the right information.[5]

The graph isomorphism problem is believed not to be NP-complete, and the best algorithm runs in quasi-polynomial time.[6][7] In 1975, Richard E. Ladner showed that if P ≠ NP, then there exist NP-intermediate problems.[8] A 1955 letter from mathematician John Nash to the National Security Agency suggested that breaking a sufficiently complex code would require time that grows exponentially with key length, a scenario that, if proven, would imply P ≠ NP.[9] Integer factorization belongs to both NP and co-NP, and as of the cited sources, no efficient algorithm for it is known.[10]

Three polls conducted by William Gasarch since 2001 show that in 2018, 88% of respondents thought P ≠ NP.[11]

What the cited sources add

The MIT News account describes P as "a set of relatively easy problems" and NP as including "what seem to be very, very hard problems".[12] It states that NP-complete problems are "fairly common, especially in large scheduling tasks".[12] Eppstein's account notes that "every NP-complete problem is in some sense a puzzle, and conversely many puzzles are NP-complete".[13] Lance Fortnow's blog explains that factoring gives "a great example of an issue that often arises in complexity, search versus decision".[14]

References

  1. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Nondeterminism is not randomness. A nondeterministic Turing machine accepts an input if at least one of its possible computation paths accepts. Equivalently, fo; "Explained: P vs. NP", MIT News Massachusetts Institute of Technology, 29 October 2009 (we also read that source) en.wikipedia.org
  2. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Hartmanis, "Gödel, von Neumann, and the P = NP problem", Bulletin of the European Association for Theoretical Computer Science, p. 101–107 (original not read by us) en.wikipedia.org
  3. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Cook, "Proceedings of the Third Annual ACM Symposium on Theory of Computing", 1971, p. 151–158; Levin, Пробл. Передачи Информ, 1973, p. 115–116 (original not read by us) en.wikipedia.org
  4. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: "MSc course: Foundations of Computer Science", www.cs.ox.ac.uk; Colbourn, Charles J., "The complexity of completing partial Latin squares", Discrete Applied Mathematics, 1984, p. 25–30; Holyer, "The NP-completeness of some edge-partition problems", SIAM J. Comput., 1981, p. 713–717 (we also read that source) en.wikipedia.org
  5. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 an (original not read by us) en.wikipedia.org
  6. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Arvind, "Graph isomorphism is in SPP", Information and Computation, 2006, p. 835–852; Schöning, "Graph isomorphism is in the low hierarchy", Journal of Computer and System Sciences, 1988, p. 312–323 (original not read by us) en.wikipedia.org
  7. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Babai, "Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures", World Sci. Publ., Hackensack, NJ, 2018, p. 3319–3336 (original not read by us) en.wikipedia.org
  8. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Ladner, "On the structure of polynomial time reducibility", Journal of the ACM, 1975, p. 151–171 See Corollary 1.1 (original not read by us) en.wikipedia.org
  9. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: NSA, "Letters from John Nash", 2012; Nash expressed skepticism that the conjecture would be proven: "The nature of this conjecture is that I cannot prove it, even for a simple type of cipher. Nor d (original not read by us) en.wikipedia.org
  10. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002. (we also read that source) en.wikipedia.org
  11. Wikipedia, "P versus NP problem" (CC BY-SA 4.0), which cites: Gasarch, "The P=?NP poll.", SIGACT News, June 2002, p. 34–47; Gasarch, "The Second P=?NP poll", SIGACT News; "Guest Column: The Third P =? NP Poll1"; "Guest Column: The Third P =? NP Poll1"; "Guest Column: The Third P =? NP Poll1"; Gasarch, "The P=?NP poll.", SIGACT News, June 2002, p. 34–47 (original not read by us) en.wikipedia.org
  12. "Explained: P vs. NP", MIT News Massachusetts Institute of Technology, 29 October 2009. facts only, no text reused. news.mit.edu
  13. Eppstein, "Computational Complexity of Games and Puzzles". facts only, no text reused. ics.uci.edu
  14. Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.. facts only, no text reused. weblog.fortnow.com

Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article P versus NP problem (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.

Related entries

Named in this entry

PolynomialComputer science

Also in the Codexery

P versus NP · Mathematical Logic And Computation

More in Complexity Theory

Theory of computationTheoretical computer sciencePushdown automatonSorting algorithmQuicksortSearch algorithmString-searching algorithmPrim's algorithmPush–relabel maximum flow algorithmSimplex algorithmShortest path problemTravelling salesman problem

Sources

Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.

Spotted an error? Know more?

Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced

Comments

Loading…
Open in the interactive codex →