Certificates and the Two Definitions of NP

Two definitions of NP circulate, and they look like descriptions of different classes. The first is machine-based: NP is what a nondeterministic Turing machine decides in polynomial time, where a nondeterministic step may branch into several successors and the machine accepts if any branch accepts. The second is checkability-based: NP is the set of languages for which there is a polynomial-time relation $R$ and a polynomial $p$ such that $x \in L$ exactly when some string $w$ of length at most $p(|x|)$ satisfies $R(x, w)$. The first sounds like a fantasy about machines that try everything at once; the second sounds like a statement about proofs. They are the same class, and the proof of equivalence is short enough to keep in mind while reading any NP-completeness argument, because every such argument silently relies on one direction or the other.

The verifier definition, stated precisely

A language $L$ is in NP if there exists a polynomial-time computable relation $R$ and a polynomial $p$ such that for every string $x$:

$$x \in L \iff \exists w,\ |w| \le p(|x|),\ R(x, w) = 1.$$

The string $w$ is called a certificate, a witness, or a proof, depending on the tradition. Three features of the definition carry all the weight.

The quantifier is existential and the certificate is chosen by the prover, not the checker. The checker is deterministic and runs in time polynomial in $|x|$, not in $|x| + |w|$. That last point requires the length bound: if certificates could be arbitrarily long, a checker running in polynomial time could not even read one, so the bound $|w| \le p(|x|)$ is what makes the running-time requirement meaningful rather than vacuous.

The requirement is one-sided. For $x \in L$ there must exist a certificate that the checker accepts. For $x \notin L$ every candidate certificate of length up to $p(|x|)$ must be rejected. Nothing is required about how hard it is to find a certificate; only that one exists and that a given one can be checked.

Completeness of the checker is not required either: it may reject a valid certificate if it is badly formed, as long as some valid certificate exists. This is why certificates can be canonical. For graph Hamiltonicity the certificate is an ordered list of vertices; a checker verifies that the list is a permutation of the vertex set and that each consecutive pair, including the wrap-around, is an edge. A malformed list is rejected, and the canonical certificate, the Hamiltonian cycle itself, is accepted.

From branching to guessing

The machine-based definition gives a nondeterministic machine a transition relation rather than a function: at each step the machine may have several legal moves, and the computation is a tree rather than a path. The machine accepts if some leaf of the tree is an accepting configuration. The time bound is the depth of the tree, and the requirement is that every branch halts within the bound.

Simulating this by a certificate is direct. Fix an input $x$ of length $n$ and a machine $M$ running in time $p(n)$. A certificate is a transcript: the sequence of nondeterministic choices made along an accepting branch, one symbol per step. Its length is at most $p(n)$, which is polynomial. The verifier replays the machine deterministically, reading the next choice from the certificate at each nondeterministic step, and accepts if the replay ends in an accepting state. If $x \in L$, an accepting branch exists and its choice sequence is a valid certificate. If $x \notin L$, no branch accepts, so no choice sequence produces an accepting replay. The verifier runs in time $O(p(n))$ plus the cost of reading the certificate, which is polynomial.

The other direction needs a bound on how many certificates there are. Given a verifier $V$ and a bound $p$, a nondeterministic machine guesses a string $w$ of length $p(n)$ symbol by symbol, which takes $p(n)$ nondeterministic steps, then runs $V(x, w)$ deterministically. The machine accepts if $V$ accepts. Because the guess is nondeterministic, some branch guesses each possible $w$, and the machine accepts exactly when a valid certificate exists.

One subtlety in that construction: guessing a string of length $p(n)$ requires knowing $p(n)$, which requires computing a polynomial in $n$. The machine computes it on a separate track of the tape before guessing, which is why the definition of NP is usually stated with $p$ a polynomial that is time-constructible: computable in time polynomial in $n$. Every polynomial with nonnegative integer coefficients that arises in practice is constructible, so the restriction costs nothing.

Certificate length is a resource, not a formality

The bound $p(|x|)$ is where the class gets its power and its limits. Shrinking the bound below polynomial changes the class; loosening it to exponential makes the class trivial.

Certificate bound	Resulting class	Example membership
$O(\log n)$	NL, via a related machine model	reachability in a directed graph is in NL, but the natural certificate is a path of length $n$
polynomial	NP	Hamiltonicity, satisfiability, subset sum with binary target
exponential	all of decidable exponential time, since the certificate can be the entire computation history	every language in EXP

The middle row is where the interesting boundary sits. The certificate for a Hamiltonian cycle is a list of $n$ vertices, each encoded in $O(\log n)$ bits, so the certificate length is $O(n \log n)$, comfortably polynomial. The certificate for a subset sum instance is a subset, encoded as a bit vector of $n$ bits. In both cases the checker does linear work in the certificate length, so the verification is linear and the class membership is immediate.

Reachability in a directed graph illustrates the lower row. The obvious certificate for a path from $s$ to $t$ is the path itself, of length up to $n$, which is polynomial and puts the problem in NP, but reachability is in fact in the much smaller class NL, because a nondeterministic machine with logarithmic space can guess the next vertex at each step and only needs to remember the current vertex. The certificate definition is tied to time, not space, and it cannot express that saving.

What NP does not say

Several common misreadings of NP follow from ignoring one clause of the definition.

NP does not mean “not polynomial”. It is not known whether P equals NP; if it does, every problem in NP has a polynomial-time decision algorithm, and the certificate definition would remain true but uninteresting. NP is defined by an upper bound on verification, not a lower bound on decision.

NP does not mean “hard to solve in practice”. A problem in NP may have a very fast algorithm; the class contains every problem in P by the trivial certificate of the empty string with a checker that ignores it. Membership in NP is an upper bound.

NP is not closed under complement in any known way. The certificate definition is asymmetric: the existential quantifier over certificates appears only in the positive case. CoNP is the class of languages whose complements are in NP, equivalently the languages with a polynomial-time relation $R$ such that $x \in L$ exactly when every string $w$ with $|w| \le p(|x|)$ satisfies $R(x, w)$. The leading quantifier is universal rather than existential, and that is the only difference. Whether NP equals CoNP is open, and it is a weaker question than whether P equals NP: if P equals NP then NP equals CoNP, but the converse is not known.

Verification being easy does not make search easy, and search being easy does not make decision easy. The relationship between deciding whether a certificate exists and producing one is not symmetric: a decision procedure yields a search procedure for the NP-complete problems, by fixing variables one at a time and re-asking the decision question, as the reduction machinery makes explicit.

A checker, and the two ways it can be wrong

The following checker for the Hamiltonian cycle decision problem is deliberately minimal: it takes a graph as an adjacency matrix and a certificate as a list of vertex indices, and it verifies both the permutation property and the edge property.

def is_hamiltonian_cycle(adj, cert):
    n = len(adj)
    if len(cert) != n:
        return False
    if sorted(cert) != list(range(n)):
        return False
    for i in range(n):
        if not adj[cert[i]][cert[(i + 1) % n]]:
            return False
    return True

The checker has two failure modes that are worth separating, because they correspond to the two clauses of the definition.

A false negative occurs when the checker rejects a certificate that actually witnesses membership. Here the sorted comparison enforces that the certificate lists each vertex exactly once; a certificate that lists a valid cycle but repeats a vertex would be rejected even though a cycle exists. This does not break the definition, because some other certificate is accepted. It does mean the checker’s accepted set is a subset of the valid certificates, which is allowed.

A false positive is fatal. If the checker accepts a certificate for a graph with no Hamiltonian cycle, then the language it defines is not the intended one, and the argument that the problem is in NP collapses. The permutation check and the edge check together rule out every way of presenting a non-cycle as a cycle: wrong length, repeated vertex, missing vertex, absent edge.

The verification cost is $O(n \log n)$ for the sort plus $O(n)$ for the edge scan, on a machine whose word size holds a vertex index. On a Turing machine the cost is polynomial but with an extra logarithmic factor for addressing, which does not affect the class.

Why the class survives re-encoding

The certificate definition is stable under changes that would break a naive definition. The verifier may be a Turing machine, a random-access machine, or a circuit family of polynomial size; the class is the same. The certificate alphabet may be binary or any fixed alphabet; encoding converts between them with a constant factor. The polynomial bound may be replaced by any bound that is polynomially equivalent, including $n^k + k$ for a fixed $k$.

What is not stable is the direction of the quantifier and the length of the certificate. Those two choices define the class, and every larger class in the polynomial hierarchy is obtained by stacking more alternating quantifiers over more certificates, the construction behind the polynomial hierarchy.