the class NP

Think of a half-finished jigsaw puzzle. Finishing it from scratch can take a very long time, but if a friend hands you a completed picture and claims it is correct, you can CHECK it almost instantly: just glance over the pieces and confirm they all fit. NP is the class of decision problems with exactly this flavour: the answer might be hard to FIND, but once a candidate answer is presented, it is easy to VERIFY. The 'yes' answers come with short evidence you can check quickly.

Formally, a decision problem (a yes/no question about an input) is in NP if there is a verifier: a deterministic algorithm that takes the input together with an extra string called a certificate (or witness), and runs in time polynomial in the size of the input. The rule is one-sided. If the true answer is 'yes', then SOME certificate exists that makes the verifier say 'yes' in polynomial time. If the true answer is 'no', then NO certificate fools it. For example, to ask 'does this graph have a clique of size 50?', a certificate is simply a list of 50 vertices; the verifier checks in polynomial time that every pair among them is joined by an edge.

NP captures an enormous range of real problems: scheduling, routing, packing, circuit design, protein folding models, puzzle solving. Almost every problem where you search for a structure that satisfies some constraints lands in NP, because a found structure is its own easy-to-check certificate. The deep mystery is whether being easy to CHECK also makes a problem easy to SOLVE. That is the P versus NP question, and nobody knows the answer. What we do know is that P is contained in NP, and that NP has hardest members, the NP-complete problems, which stand or fall together.