From 'solve it' to 'check it'
The previous guide handed you a clean menu of yes/no problems and a first picture of the class P — the problems a single algorithm can decide in polynomial time. It also gave a first, rougher gesture at NP. This guide makes that gesture exact, and the key move is to stop asking 'can we find the answer fast?' and start asking 'if someone claims the answer is yes and hands us evidence, can we check it fast?' Those are wildly different questions, and the gap between them is the whole story of this rung.
Make it concrete with a Sudoku puzzle. Filling in a blank grid from scratch feels genuinely hard; you may have to try, backtrack, and try again. But if a friend slides a completed grid across the table and claims it solves the puzzle, checking them is trivial: scan every row, column, and box, confirm each holds 1 through 9 with no repeats. That check is a handful of passes over the grid — fast and mechanical. Solving is hard; checking a proposed solution is easy. NP is the precise name for problems where this is true.
Certificates and the verifier
Let us name the two pieces. The 'evidence' your friend hands you is a certificate (also called a witness or proof) — a string of extra information that, for a yes-instance, points to why the answer is yes. The mechanical checker is the verifier: an ordinary deterministic algorithm that takes both the original instance and the certificate, and outputs accept or reject. The pairing of these two is the heart of the verifier definition of NP.
The definition has to be stated with care, because a sloppy version would let every problem in. A problem is in NP if there exists a verifier V, running in time polynomial in the instance size, with two properties. Completeness: if the instance is a yes-instance, then some certificate makes V accept. Soundness: if the instance is a no-instance, then no certificate — none whatsoever — can fool V into accepting. The verifier must be both generous enough to recognize a real proof and strict enough that fake proofs always fail.
Two size constraints make this honest, and skipping either one breaks the class. First, the verifier runs in polynomial time. Second — this is the subtle one — it follows that only certificates of polynomial length can matter: a verifier that runs in time p(n) cannot even finish reading a certificate longer than p(n) symbols, so without loss of generality the certificate is bounded by a polynomial in n. If you allowed exponentially long certificates, you could smuggle the entire answer table in and the class would collapse into nonsense. Short proof, fast check: both words are load-bearing.
A worked verifier: SAT
The cleanest example is the satisfiability problem, SAT. An instance is a Boolean formula over variables x1, x2, ..., xn — say (x1 OR NOT x2) AND (x2 OR x3) AND (NOT x1 OR NOT x3). The question is the yes/no decision: does there exist an assignment of true/false to the variables that makes the whole formula true? Finding such an assignment seems to demand searching among 2^n possibilities. But verifying one is almost embarrassingly cheap.
Here the certificate is simply a proposed assignment — one true/false value per variable, exactly n bits long. The verifier plugs those values into the formula and evaluates it: walk each clause, check whether at least one of its literals came out true, and accept only if every clause is satisfied. Evaluating a formula of length m takes O(m) time, comfortably polynomial. Now check the two properties against the definition.
- Completeness: if the formula is satisfiable, then by definition a satisfying assignment exists — hand that assignment as the certificate, and the verifier evaluates the formula to true and accepts.
- Soundness: if the formula is unsatisfiable, then NO assignment makes it true, so whatever string is offered as a certificate either fails to evaluate the formula to true or is not a valid assignment — the verifier rejects every time.
- Size: the certificate is n bits and the check is O(m); both are polynomial in the instance, so SAT is in NP by the verifier definition.
Why P sits inside NP
The verifier definition makes one fact almost free, and it is worth seeing because beginners often find it surprising. Every problem in P is also in NP. If you can already solve a problem in polynomial time on your own, then you do not even need a useful certificate to verify a yes-answer: build a verifier that ignores whatever certificate it is handed, runs your own polynomial-time solver on the instance, and accepts exactly when the solver says yes.
That verifier is genuinely a valid NP verifier. It runs in polynomial time (it is just your solver). On a yes-instance, every certificate makes it accept, so certainly some certificate does — completeness holds. On a no-instance, no certificate makes it accept, because the solver itself says no regardless of the ignored certificate — soundness holds. So P is contained in NP, written P ⊆ NP. The certificate became a free formality precisely because solving was already easy.
The reverse direction is the trillion-dollar question. Is every problem whose yes-answers are easy to check also one whose answers are easy to find? That is asking whether NP ⊆ P, which together with P ⊆ NP would mean P = NP. Nobody knows. The honest status is that P versus NP is open — widely believed to be P ≠ NP, but believed is not proved. Keep that humility front of mind: the rest of this rung shows how the field organizes its knowledge around a question it cannot yet answer.
Nondeterminism: the same idea, a lucky guesser
There is a second, older way to define NP that looks completely different yet describes the very same class — and seeing why they agree deepens the whole picture. Recall the distinction from the foundations rung between a deterministic and a nondeterministic machine. A deterministic algorithm has exactly one next step at every moment. A nondeterministic machine is a thought-experiment that, when it reaches a choice, is allowed to branch into all options at once, and it is said to accept the input if any single branch reaches an accepting state.
The friendly cartoon is a machine that guesses. At each branching point it magically guesses the right choice, as if infinitely lucky, then verifies that its guesses pan out. NP is the class of decision problems a nondeterministic machine can decide in polynomial time. The picture is exactly the guess-and-verify pattern: guess a candidate, then deterministically check it. And that is why the two definitions coincide — the sequence of lucky guesses is the certificate.
Trace the equivalence in both directions and it clicks. A nondeterministic machine that decides a problem in polynomial time makes at most polynomially many guesses along any branch; write those guessed bits down and you have a polynomial-length certificate, and replaying the machine while reading them off the certificate is a deterministic polynomial-time verifier. Conversely, given a verifier, build a nondeterministic machine that guesses a certificate bit by bit and then runs the verifier — it accepts on some branch exactly when an accepting certificate exists. Both definitions carve out the identical class, the nondeterministic view and the verifier view being two faces of one coin.
nondeterministic decide(instance):
cert = GUESS a polynomial-length string # the lucky guess
return Verifier(instance, cert) # deterministic, poly-time
# accepts <=> SOME guessed cert makes Verifier accept
# <=> instance is a yes-instanceWhat this buys us, and what it does not
The verifier lens reframes a whole zoo of stubborn problems under one roof. SAT, finding a Hamiltonian cycle in a graph, deciding subset-sum, graph coloring, packing a knapsack to hit a target value — each looks like a different beast, yet each shares the SAT shape: a yes-answer carries a short certificate (a tour, a chosen subset, a coloring) that a simple deterministic verifier can check in polynomial time. That shared structure is the reason the next guides can compare their difficulties at all.
But be precise about what membership in NP does and does not claim, because the words invite over-reading. Saying a problem is in NP says only that yes-answers have short, checkable proofs. It says nothing about how to find a certificate, and emphatically does not say the problem is hard — every problem in P is in NP too, as we saw. The honest summary: NP is an upper structure on checkability, not a verdict of difficulty. The difficulty story arrives later, when reductions let us rank these problems against each other.
And keep the asymptotic caveats from the early rungs in view. 'Polynomial-time verifier' is an asymptotic, machine-independent yardstick: it tells you the check scales gracefully, not that it is fast for the n on your desk today, since a high-degree polynomial like n^6 with a big constant can be sluggish at modest sizes. The boundary between polynomial and exponential growth is the line the whole theory draws — coarse on purpose, robust precisely because it ignores constants. The next guide turns to reductions, the tool that finally lets us say one problem is at least as hard as another.