Difficulty: Intermediate | Prerequisites: Basic Turing machine definitions, understanding of P vs NP distinction, familiarity with polynomial-time algorithms.
This material sits at the heart of computational complexity theory: determining which problems belong to the classes P and NP, and learning to prove membership (or non-membership) rigorously. The core skill is constructing a polynomial-time verifier with a certificate, which is the standard technique for showing a language is in NP. You should already be comfortable with Turing machines, big-O notation, and the informal distinction between "finding a solution" and "checking a solution." If those feel shaky, revisit your notes on decidability and time complexity first.
Most exam questions on this topic ask you to either build a verifier (certificate + verification steps + correctness + time analysis) or explain why a verifier cannot work. The pattern is highly repeatable once you see it a few times, which is exactly what these notes walk through.
To prove a language is in NP, you propose a certificate (a short proof that a "yes" instance is correct) and build a polynomial-time verifier that checks it. If the certificate might be too large or the verifier too slow, the language may fail the NP requirement. These notes cover five worked examples: two non-membership arguments and three full NP-membership proofs (Hamiltonian Cycle, Graph Isomorphism, Compositeness).
P (Polynomial Time)
The class of decision problems solvable by a deterministic Turing machine in time O(n^k) for some constant k.
In simple terms, these are problems a computer can both find and verify answers to quickly.
NP (Nondeterministic Polynomial Time)
The class of decision problems for which a "yes" answer can be verified in polynomial time, given an appropriate certificate.
Think of it as: you might not be able to find the answer fast, but if someone hands you a proposed answer, you can check it fast.
Certificate (also: witness, proof)
A piece of evidence that accompanies a "yes" instance and lets the verifier confirm correctness. It must be polynomial in size relative to the input.
In simple terms, it is the cheat sheet you hand to the checker so they can say "yes, this is correct" without solving the problem from scratch.
Verifier
A deterministic Turing machine V that takes an input x and a certificate c, and accepts if and only if c is valid proof that x is a "yes" instance. V must run in polynomial time in |x|.
Think of it as the grader: it does not solve the problem, it just checks the proposed solution.
Polynomial-time reduction
A transformation from one problem to another that runs in polynomial time and preserves yes/no answers. Used to relate the difficulty of problems.
Hamiltonian Cycle (Ham-Cycle)
A cycle in a graph that visits every vertex exactly once and returns to the starting vertex. The decision problem asks whether a given graph contains such a cycle.
Graph Isomorphism
Two graphs G and G' are isomorphic if there exists a bijection between their vertex sets that preserves all edges. The decision problem asks whether such a mapping exists.
Not-Prime (Compositeness)
The language of all natural numbers that are not prime, i.e. numbers that have a factor besides 1 and themselves. Equivalently, composite numbers.
The language L_ACC fails the NP membership test because its verifier is not efficient.
To belong to NP, a language needs a verifier V that runs in time polynomial in the input size |x|.
For L_ACC, the certificate C can be much larger than the input (the machine M and string x combined).
Because C is unbounded relative to |x|, the verifier cannot be guaranteed to run in polynomial time.
Conclusion: we cannot construct a polynomial-time verifier, so L_ACC is not in NP.
The key insight is that NP requires the certificate itself to be polynomially bounded in the input length. If the certificate can be arbitrarily large, the verification step blows past polynomial time even if the checking logic is simple.
The algorithm F for First-Digit-Factorial does not guarantee polynomial-time execution for all inputs, so the language is not in P.
Consider when n! = 10^k for some k. Here k is the number of digits in n!.
The number of digits in n! grows roughly as O(n log n), which is super-polynomial relative to the input size (the binary representation of n has about log n bits).
An algorithm that explicitly computes or iterates over all digits of n! would take time exponential in the input length.
To place First-Digit-Factorial in P, you would need a fundamentally different algorithm that avoids computing the full factorial, one that runs in time polynomial in log n (the input size).
This is a common exam trap: an algorithm that looks efficient for small n may still be exponential when measured against input length rather than input value.
To show Hamiltonian Cycle is in NP, we construct a verifier V with a certificate.
Certificate: a sequence of edges c that claims to form a Hamiltonian cycle in G.
Verifier V on input ⟨G, c⟩:
For every edge (u, v) in c, check that (u, v) is an edge in G. If any edge is missing, reject.
Check that c visits every vertex of G exactly once and forms a cycle (returns to the start vertex).
If all checks pass, accept.
Correctness:
If G has a Hamiltonian cycle, there exists a certificate c (the cycle's edges) that makes V accept.
If G has no Hamiltonian cycle, no certificate can pass all the checks, so V always rejects.
Time complexity: O(V + E). Checking that each edge in c exists in G takes at most E lookups. Checking that every vertex appears exactly once takes V operations. Both are polynomial in the input size.
To show Graph Isomorphism is in NP, we construct a verifier with the isomorphism itself as the certificate.
Certificate: a bijection γ : V → V' mapping vertices of G to vertices of G'.
Verifier V on input ⟨G, G', c⟩:
Check that c = γ is a bijective function between V and V'.
For each edge (a, b) in E: check that (γ(a), γ(b)) is in E'. If not, reject.
For each edge (a', b') in E': check that (γ⁻¹(a'), γ⁻¹(b')) is in E. If not, reject.
If all checks pass, accept.
Correctness:
If G and G' are isomorphic, a valid bijection γ exists and V will accept.
If they are not isomorphic, no bijection can satisfy both edge-preservation checks, so V rejects.
Time complexity: O(E). Step 2 iterates over |E| edges, step 3 over |E'| edges. Together that is 2|E| operations (since isomorphic graphs have equal edge counts), which is O(E).
To show Not-Prime is in NP, we use a factorisation as the certificate.
Certificate: a pair of factors (a, b) such that a × b = n and 1 < a, b < n.
Verifier V on input ⟨n, c⟩:
Check that the product of the factors in c equals n.
Check that each factor a and b satisfies 1 < a < n and 1 < b < n.
If both checks pass, accept. Otherwise, reject.
Correctness:
If n is composite, a valid factorisation exists, so V will accept.
If n is prime, no pair (a, b) with 1 < a, b < n can multiply to n, so V always rejects.
Time complexity: multiplication of two numbers each at most n takes O(log² n) with standard algorithms. Comparing factors to n is O(log n). Both are polynomial in the input size (the number of bits needed to write n).
Students often think "NP" means "not polynomial" or "exponential." It does not. NP means there is a polynomial-time verifier, not necessarily a polynomial-time solver.
Students sometimes forget that the certificate must be polynomial in size relative to the input. A correct verifier with an unbounded certificate does not prove NP membership.
A common error is measuring time complexity relative to the value of the input rather than the length (number of bits). For First-Digit-Factorial, n may be small, but n! has exponentially many digits relative to log n.
Students occasionally confuse "proving L is in NP" with "proving L is NP-complete." Membership only requires a verifier. Completeness additionally requires showing every NP language reduces to L.
⚠️ The three-part structure (certificate, verifier algorithm, correctness + time analysis) appears on nearly every NP-membership exam question. Practise writing all three parts, not just the verifier.
⚠️ Be precise about what the certificate is. "The solution" is too vague. Name the data structure: a sequence of edges, a bijection, a pair of factors.
⚠️ Exams often include a trick problem where the certificate or verifier looks fine but fails the polynomial-time bound. L_ACC and First-Digit-Factorial are examples of exactly this pattern.
⚠️ Time complexity must be stated in terms of the input size (typically the encoding length), not in terms of a numeric parameter like n.
True or False: A language is in NP if there exists some algorithm that solves it, regardless of runtime. ___
True or False: The certificate for an NP proof must be polynomial in size relative to the input. ___
Fill in the blank: To prove L ∈ NP, you must construct a polynomial-time ___ and describe the ___.
True or False: If a verifier V is correct but runs in exponential time, the language is still in NP. ___
Fill in the blank: The certificate for Graph Isomorphism is a ___ between the vertex sets.
Answers: 1. False. 2. True. 3. verifier; certificate. 4. False. 5. bijection.
Q: Describe the certificate and verifier you would use to prove that the Hamiltonian Cycle problem is in NP.
A: Certificate: a sequence of edges forming the proposed cycle. Verifier: check that every edge in the sequence exists in G, that every vertex of G appears exactly once, and that the sequence forms a cycle. This runs in O(V + E) time.
Q: Why does L_ACC fail to be in NP, even though a verifier V exists?
A: The certificate C can be much larger than the input (M, x), so the verifier's runtime is not bounded by a polynomial in the input size. NP requires the verifier to run in time polynomial in |x|, and an unbounded certificate breaks that requirement.
Q: Explain why First-Digit-Factorial is not known to be in P, referencing the distinction between input value and input size.
A: The input n is encoded in about log n bits. The number n! has roughly n log n digits, which is exponential in log n. Any algorithm that must process all digits of n! runs in time exponential in the input length, so it is not polynomial-time.
Q: What is the certificate for proving Graph Isomorphism ∈ NP, and what must the verifier check?
A: The certificate is a bijection γ : V → V'. The verifier checks that for every edge (a, b) in G, (γ(a), γ(b)) is an edge in G', and vice versa. This takes O(E) time.
Q: For the Not-Prime problem, what certificate would you provide and how does the verifier use it?
A: The certificate is a pair of integers (a, b) with 1 < a, b < n and a × b = n. The verifier multiplies a and b, confirms the product equals n, and confirms both factors are strictly between 1 and n. All operations are polynomial in the number of bits of n.
This material connects directly to NP-completeness: once you can prove a problem is in NP, the next question is often whether it is NP-complete (via reductions). Hamiltonian Cycle, for instance, is one of the classic NP-complete problems.
The verifier/certificate framework also connects to the P vs NP question. If P = NP, then every problem with an efficient verifier also has an efficient solver, which would collapse the distinction these proofs rely on.
The closure properties of P and NP (covered in the companion notes) build on the same machinery: verifiers, polynomial-time bounds, and certificates.
NP membership proof, polynomial-time verifier, certificate witness, Hamiltonian cycle NP, graph isomorphism NP, compositeness NP, Not-Prime NP, NP verification, verifier construction, complexity class membership, L_ACC not in NP, First-Digit-Factorial not in P, EECS 376, Foundations of Computer Science, University of Michigan, computational complexity, decision problem, nondeterministic polynomial time