P = NP problem

related topics
{math, number, function}
{theory, work, human}
{work, book, publish}
{law, state, case}

The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer. It was introduced in 1971 by Stephen Cook in his paper "The complexity of theorem proving procedures"[2] and is considered by many to be the most important problem in the field.[3] 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.

In essence, the question P = NP? asks:

The theoretical notion of quick used here is an algorithm that runs in polynomial 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 may be possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP.

Consider the subset sum problem, an example of a problem that is easy to verify, but whose answer may be difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero" can be quickly verified with three additions. However, finding such a subset in the first place could take more time; hence this problem is in NP (quickly checkable) but not necessarily in P (quickly solvable).

An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that some NP problems are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

Contents

Full article ▸

related documents
Finite set
Imaginary unit
Multiplication
Exponentiation by squaring
Quadratic equation
General linear group
Relational database
Riemannian manifold
Semidirect product
Category theory
Busy beaver
Communication complexity
Control flow
AWK
Monoid
Exponential function
Interpolation
Operator
Lie algebra
Set (mathematics)
Polyomino
Metric space
Stochastic process
Dirac delta function
Dylan (programming language)
Taylor's theorem
Extended Euclidean algorithm
Vigenère cipher
Template (programming)
Vacuous truth