View source for P versus NP problem

The '''P versus NP problem''' is a major unsolved problem in [[computer science]].

Informally speaking, it asks:

 If the solution to a problem is easy to check for correctness, is the problem easy to solve?

== Description ==

It was essentially first mentioned in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]]. 

Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time (see [[Time complexity]]).

The precise statement of the P versus NP problem was introduced in 1971 by [[Stephen Cook]] in his seminal paper "The complexity of theorem proving procedures" and is considered by many to be the most important open problem in the field.

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

== Quickly ==

The informal term ''quickly'', used above, means the existence of an [[algorithm]] for the task that runs in [[polynomial time]], i.e., that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, [[exponential time)]].

The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P".

For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly.

The class of questions for which an answer can be verified in polynomial time is called NP, which stands for "nondeterministic polynomial time."

== See also ==

* [[Computer science]]
* [[Computation]]
* [[Game complexity]]
* [[Time complexity]]
* [[Unique games conjecture]]
* [[Unsolved problems in computer science]]
* [[Unsolved problems in mathematics]]

== External links ==

* [https://en.wikipedia.org/wiki/P_versus_NP_problem P versus NP problem] @ Wikipedia

[[Category:Computer science]]
[[Category:Computation]]