p & np

The relationship between the complexity classes P (Polynomial time) and NP (Nondeterministic Polynomial time) is an unsolved problem in theoretical computer science, and is considered by many theoretical computer scientists to be the most important problem in the field.[2] The Clay Mathematics Institute, which is dedicated to increasing and disseminating mathematical knowledge, has included it in its list of Millennium Prize Problems; anyone who provides a satisfactory solution to the problem may be entitled to a USD $1,000,000 prize.[3][4]

In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"? The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice.

Consider the subset sum problem, an example of a problem which is easy to verify but whose answer is suspected to be theoretically 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. The information needed to verify a positive answer is also called a certificate. Given the right certificates, "yes" answers to our problem can be verified in polynomial time, so this problem is in NP.

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.

The restriction to yes/no problems is unimportant; when more complicated answers are allowed the extension to function problems becomes FP = FNP, which has been proven to be equivalent to P = NP.[5]