title: "Verifier"

Verifier

Definition. A verifier for a language $A$ is an algorithm $V$ such that $A = \{w : V$ accepts $\langle w, c \rangle$ for some string $c\}$. The string $c$ is a certificate for $w$, and $V$ is a polynomial-time verifier if it runs in time polynomial in $|w|$ alone.

Measuring in $|w|$ rather than $|w| + |c|$ means a polynomial-time verifier can read only polynomially much of the certificate, so the usual restriction to short certificates is a consequence rather than an extra hypothesis. The quantifiers are asymmetric: membership is witnessed by one certificate, non-membership is a claim about all of them. $\mathsf{NP}$ is exactly the class of languages with polynomial-time verifiers, equivalently those decided by a nondeterministic Turing machine in polynomial time, since a certificate records the choices a lucky branch would make. Defined in Lecture 10.