the class NP
/ en-pee /
Some yes/no questions are hard to ANSWER from scratch but easy to CHECK once someone hands you the answer with a hint. 'Does this giant Sudoku have a solution?' might take ages to decide alone — but if a friend shows you a filled grid, you can verify in a flash whether it is a valid solution. 'Is this number a product of two large primes p and q?' is hard to crack, yet trivial to check if someone whispers p and q. NP is the class of all decision problems with exactly this flavour: a 'yes' answer always comes with a short hint (a certificate) that lets you confirm it quickly.
Precisely, a decision problem is in NP if there is a polynomial-time VERIFIER: a deterministic algorithm V that takes the input x and an extra string c (the certificate, of length polynomial in |x|), and runs in polynomial time, with this property — if the true answer for x is 'yes', then SOME certificate c makes V accept; and if the answer is 'no', then NO certificate makes V accept. So 'yes' instances have a convincing short proof you can check fast, while 'no' instances cannot be faked by any proof. An equivalent definition uses nondeterminism: a machine that may 'guess' the certificate in one lucky stroke and then verify it; that guess-and-check picture is where the historical name 'nondeterministic polynomial time' comes from. Note the asymmetry baked in: NP is about easy-to-check YES answers; the matching guarantee for NO answers defines a different class, co-NP.
Every problem in P is also in NP (if you can SOLVE it fast, you can certainly CHECK it fast — just ignore the hint and re-solve), so P sits inside NP. The million-dollar open question is whether they are actually equal: is every quickly-checkable problem also quickly-solvable? Almost everyone believes P is not equal to NP, but no one has proved it. NP is enormous and practical — it contains satisfiability, the travelling salesman decision problem, graph colouring, scheduling, and thousands more — which is exactly why understanding its internal structure (P, NP-complete, NP-intermediate) matters so much.
Subset-sum: given numbers {3, 34, 4, 12, 5, 2} and target 9, is there a subset summing to 9? Finding one might mean searching many subsets. But if a certificate says '{4, 5}', you just add 4 + 5 = 9 and check the items are in the set — a few steps. The easy-to-check 'yes' proof is what places subset-sum in NP.
NP: a 'yes' always has a short certificate that a polynomial-time verifier can confirm.
A common myth: NP means 'non-polynomial' or 'hard'. It does NOT — it stands for nondeterministic polynomial and is about EASY checking of yes-answers. P is a subset of NP, so 'in NP' includes all the easy problems too; NP is not the set of intractable problems.