The Class NP & Verifiers

Short certificates, poly-time verifiers, and nondeterminism define NP.

The idea

The class $\mathsf{NP}$ consists of the problems whose yes-answers can be checked in polynomial time, whether or not they can be found that quickly. Finding a route through a large network that visits every node once may take a very long time; confirming that a proposed route does so takes moments.

The object checked is a certificate (or witness) $c$, and the checker is a verifier: a deterministic polynomial-time machine $V$ that reads the input $x$ together with $c$ and accepts or rejects. Two conditions make this a definition. The certificate must be short — its length bounded by a polynomial $p$ in the length of $x$ — since otherwise an exhaustive table could pass as a proof. And $V$ must be impossible to fool: a member of $L$ has some certificate it accepts, and a non-member has none. So $L$ is in $\mathsf{NP}$ when there exist such a $V$ and $p$ with

$x \in L \iff \exists\, c,\ |c| \le p(|x|),\ \text{for which } V(x, c) \text{ accepts.}$

The condition is one-sided: it demands a short proof of membership and asks nothing about non-members. And no one is required to produce $c$. A nondeterministic machine may guess the certificate and then run $V$ on it, and this description picks out exactly the same languages, which is why $\mathsf{NP}$ abbreviates nondeterministic polynomial time. The figure shows the two views of one acceptance: an accepting branch of guesses, and the same branch written down as the certificate $c$ that $V(x, c)$ replays.

Ways to work on it

• Walkthrough. Certificates, verifiers, and the nondeterministic view of NP.
• Practice. Identify the certificate for a standard NP problem.
• Hardest. Reason about search size and the one-sided certificate condition.

Not sure where to start? Take the ten-question placement test.