Certificates and Class NP

Certificates: Short Evidence for a Yes-Answer

Many graph questions ask whether a graph has some structure: a clique of a specified size, a small vertex cover, or a cycle through every vertex. A direct search may require trying many possibilities. A certificate is a proposed solution that can be checked efficiently. The key point is that checking one proposal can be much easier than finding a proposal or establishing that none exists.

We use the standard input-encoding viewpoint: a decision problem is a set of finite binary strings, and the input length is the number of bits in the string. For graph examples, take an adjacency-matrix encoding of a finite simple graph, together with any integer parameter in binary. Such an encoding explicitly represents the vertices and their adjacencies; its length is at least proportional to the number of vertices. Encodings that do not represent a valid instance are rejected. A running time is polynomial if it is bounded by a polynomial in the input length.

The two parts of the condition matter. The certificate must have length bounded by a polynomial in the input length, and the verifier must run in polynomial time. The verifier is deterministic: it checks a supplied certificate. The existential phrase “there exists a certificate” means that a yes-instance needs at least one accepting certificate; it does not require every proposed certificate to pass. A no-instance must have no certificate that passes.

This definition does not say that the certificate is easy to discover. It also does not say that the verifier proves a no-answer by checking a failed certificate. In the graph examples below, a certificate describes the requested structure, and the verifier checks that the description really has the required properties.

Three Graph Problems and Their Verifiers

For these examples, let \(G=(V,E)\) be a finite simple undirected graph. A clique is a set of vertices every two distinct members of which are adjacent. A vertex cover is a set of vertices containing at least one endpoint of every edge. A Hamiltonian cycle is a cycle that visits every vertex exactly once before returning to its starting vertex. The decision problems ask, respectively, whether \(G\) has a clique of size at least \(k\), a vertex cover of size at most \(k\), or a Hamiltonian cycle. For the first problem take \(1\le k\le |V|\); for the second take \(0\le k\le |V|\); and for the third take \(|V|\ge3\).

A subset of \(V=\{1,\dots,n\}\) can be described by an \(n\)-bit string: bit \(i\) is 1 exactly when vertex \(i\) is included. Thus a proposed clique or cover has a certificate of length \(n\). A Hamiltonian cycle can be described by an ordered list of the \(n\) vertex labels; with fixed-width labels this uses \(O(n\log n)\) bits. Since the graph encoding has length at least proportional to \(n\), these certificate lengths are polynomial in the input length.

Proof. For clique, the verifier checks that the certificate is a valid \(n\)-bit vector, counts its 1-bits, and rejects if the count is less than \(k\). It then checks every pair of distinct selected vertices against the adjacency matrix, accepting exactly when every such pair is adjacent. If it accepts, the selected vertices form a clique of size at least \(k\), so the graph is a yes-instance. Conversely, if the graph has a clique of size at least \(k\), the bit vector marking the vertices of that clique passes both checks. The verifier checks at most \(n(n-1)/2\) pairs, so its running time is polynomial.

For vertex cover, the verifier checks that the certificate is an \(n\)-bit vector and that it has at most \(k\) 1-bits. It then checks each edge \(uv\in E\), accepting exactly when at least one of \(u,v\) is selected. Acceptance means that the selected set has size at most \(k\) and contains an endpoint of every edge, so it is a vertex cover. If a vertex cover of size at most \(k\) exists, its bit vector passes these checks. Scanning all pairs in the adjacency matrix, or all listed edges, takes polynomial time.

For Hamiltonian cycle, the verifier checks that the certificate is a list of \(n\) labels, each in \(\{1,\dots,n\}\), with every label appearing exactly once. It then checks that each consecutive pair in the list is an edge and that the last and first labels are also adjacent. If it accepts, the list gives a cycle visiting every vertex exactly once. Conversely, writing the vertices of any Hamiltonian cycle in cyclic order gives a certificate passing all the checks. Checking label validity, uniqueness and the \(n\) required adjacencies takes polynomial time; even comparing every pair of labels to test uniqueness takes only \(O(n^2)\) comparisons. Each verifier has polynomial certificate length and polynomial running time. \(\square\)

Worked Certificates

Why \(P\) Is Contained in \(NP\)

The class \(P\) consists of languages that a deterministic algorithm decides in polynomial time. “Decides” means the algorithm halts on every input and returns the correct yes-or-no answer. A polynomial-time decision algorithm can serve as a verifier: it can decide the input itself and need not make use of any certificate.

Proof. Let \(L\in P\). By the definition of \(P\), there is a deterministic polynomial-time algorithm \(A\) that accepts exactly the strings in \(L\). Construct a verifier \(V\) that accepts only the empty certificate and, on that certificate, runs \(A\) on its input \(x\), accepting exactly when \(A\) accepts. The empty certificate has length zero, which is bounded by a polynomial in \(|x|\), and \(V\)'s running time is polynomial in \(|x|\). If \(x\in L\), then \(A\) accepts, so the empty certificate is accepted. If \(x\notin L\), then \(A\) rejects, and no certificate is accepted because \(V\) rejects nonempty certificates as well. Hence \(x\in L\) exactly when some polynomially bounded certificate is accepted by \(V\). Thus \(L\in NP\), proving \(P\subseteq NP\). \(\square\)

This inclusion uses no assumption that a certificate helps the verifier. It only shows that every problem already decidable in polynomial time has a polynomial-time verifier. It does not establish that \(P=NP\), nor does it establish that any particular graph problem lies outside \(P\).

Common Pitfall: Passing One Check Is Not Enough

A certificate must satisfy every condition in the verifier, not merely the easiest one. In the clique example, the bit vector \(11100\) selects \(\{1,2,3\}\), so it has three selected vertices, meeting the size threshold \(k=3\). But the required pair \(13\) is not in \(E=\{12,23,24,34,45\}\). The verifier must reject: the selected set is not a clique. By contrast, \(01110\) selects \(\{2,3,4\}\), and its pairs \(23,24,34\) are all edges.

There is a related distinction between a certificate and an optimality proof. A vertex-cover certificate of size at most \(k\) proves that such a cover exists; it does not prove that no smaller cover exists. Likewise, a clique certificate proves the existence of the displayed clique, not that it is maximum. The yes-answer is supported by one valid witness, while ruling out all smaller or better alternatives is a different task.

The certificate viewpoint is useful because it gives a precise meaning to “easy to check”: the witness is polynomial in input length, and a deterministic verifier checks it in polynomial time. This makes it possible to discuss a broad class of decision problems without requiring that their solutions be found by the verifier. For graph problems, the certificate is often a direct description of the requested object, and the verification consists of checking its defining properties.