The Class NP

NP is the class of problems whose yes-answers can be verified by a deterministic algorithm in polynomial time given a short certificate.

Verification, not solution

NP (nondeterministic polynomial time) contains decision problems where, if the answer is yes, there is a proof or certificate that a deterministic algorithm can check in polynomial time. Finding the certificate may be hard; checking it is easy. That asymmetry is the heart of NP.

Two equivalent definitions

Kronos motion — confinement time

Verifier view: a yes-instance has a polynomial-size certificate checkable in polynomial time
Machine view: a nondeterministic Turing machine accepts in polynomial time by guessing the certificate

A canonical example

For Boolean satisfiability, a certificate is an assignment of true/false to the variables. Checking whether that assignment satisfies the formula is a quick linear scan. Searching all assignments is exponential, but verifying one is cheap. This is the NP pattern exactly.

P inside NP

Every problem in P is in NP: if you can solve it quickly, you can verify it quickly by ignoring the certificate and just solving. Whether the reverse holds, whether easy-to-check implies easy-to-solve, is the P vs NP question.

The hardest problems in NP

Within NP sit the NP-complete problems, the hardest members, to which every other NP problem reduces. If any one of them has a polynomial-time algorithm, then all of NP does, and P would equal NP.

Common misreadings

NP does not stand for "non-polynomial"; it stands for nondeterministic polynomial. NP problems are not by definition intractable, and P is a subset of NP. The intractable-looking ones are the NP-complete and NP-hard problems, for which no efficient algorithm is known.