a verifier

A verifier is the airport security agent of complexity theory. It does not have to figure out your whole trip; it just inspects your boarding pass and ID and quickly decides whether they check out. Given an input and a proposed piece of evidence, a verifier reads both and gives a fast yes/no verdict: yes, this evidence really does prove the answer is 'yes'; or no, it does not. The verifier never has to discover the evidence itself, which is what makes its job easy.

Precisely, a verifier for a problem is a deterministic algorithm V that takes two arguments: the original input x and a certificate c. We say V verifies the problem if, for every input x, the true answer is 'yes' exactly when there EXISTS a certificate c such that V accepts the pair (x, c). For NP we add the resource bound: V must run in time polynomial in the length of x, and (as a consequence) it can only look at a certificate of polynomial length. The polynomial bound on the input also caps the useful certificate size, because V cannot even read a certificate longer than its own running time.

The verifier viewpoint is the cleaner of the two standard definitions of NP, because it never mentions strange machines that 'guess'. It reframes hardness as a question about evidence: a problem is in NP exactly when its yes-answers admit short, efficiently-checkable proofs. This is also why NP feels so natural in practice. A satisfying assignment for a formula, a valid tour for a salesman, a proper colouring of a map, are all certificates, and writing the checker that inspects one is usually routine. Designing the verifier is how you typically PROVE a problem belongs to NP.