Editing P versus NP problem (section)

{{short description|Unsolved problem in computer science}}
{{pp-move-indef}}
{{unsolved|computer science|If the solution to a problem is easy to check for correctness, must the problem be easy to solve?}}
{{Use dmy dates|date=October 2020}}
{{Millennium Problems}}

The '''P versus NP problem''' is a major [[List of unsolved problems in computer science|unsolved problem]] in [[theoretical computer science]]. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

Here, "quickly" means an algorithm exists that solves the task and runs in [[polynomial time]] (as opposed to, say, [[exponential time]]), meaning the task completion time is [[upper bound|bounded above]] by a [[polynomial function]] on the size of the input to the algorithm. The general class of questions that some [[algorithm]] can answer in polynomial time is "[[P (complexity)|P]]" or "class P". For some questions, there is no known way to find an answer quickly, but if provided with an answer, it can be verified quickly. The class of questions where an answer can be ''verified'' in polynomial time is [[NP (complexity)|"NP"]], standing for "nondeterministic polynomial time".<ref group="Note">A [[nondeterministic Turing machine]] can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.</ref>

An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If P&nbsp;≠&nbsp;NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

The problem has been called the most important open problem in [[computer science]].<ref>{{cite journal | last1 = Fortnow | first1 = Lance | author-link = Lance Fortnow | year = 2009 | title = The status of the P versus NP problem | url = http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78–86 | doi = 10.1145/1562164.1562186 | citeseerx = 10.1.1.156.767 | s2cid = 5969255 | access-date = 26 January 2010 | archive-url = https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | archive-date = 24 February 2011 }}</ref> Aside from being an important problem in [[computational theory]], a proof either way would have profound implications for mathematics, [[cryptography]], algorithm research, [[artificial intelligence]], [[game theory]], multimedia processing, [[philosophy]], [[economics]] and many other fields.<ref>{{Cite book|title=The Golden Ticket: P, NP, and the Search for the Impossible|last=Fortnow|first=Lance|publisher=Princeton University Press|year=2013|isbn=9780691156491|location=Princeton, NJ}}</ref>

It is one of the seven [[Millennium Prize Problems]] selected by the [[Clay Mathematics Institute]], each of which carries a US$1,000,000 prize for the first correct solution.