Source: Discussion Worksheet 09, EECS 376, University of Michigan
Difficulty: Intermediate | Prerequisites: Familiarity with P, NP, polynomial-time reductions, and the definition of NP-Completeness.
This worksheet sits at the junction of complexity theory and algorithm design. By now in EECS 376, you have seen reductions, the classes P and NP, and the notion of NP-Completeness. Here you are asked to reason carefully about what approximation guarantees do and do not promise, what a verifier does when it receives a valid input, and the subtle difference between deciding membership and verifying a certificate. If any of those phrases feel unfamiliar, revisit the lecture notes on P, NP, and NP-Completeness before working through these questions.
A 2-approximation for a minimisation problem guarantees cost at most 2× optimal, but it does not promise equality on every input. An NP-Complete language has certificates that a verifier sometimes accepts (not always, because the wrong certificate for a valid input can still fail). Verifying that a given cycle is Hamiltonian can be done in polynomial time, placing that verification language squarely in P.
Approximation algorithm (α-approximation)
An efficient algorithm whose output is guaranteed to be within a factor α of the optimal solution on every input. For a minimisation problem, |A(x)| ≤ α · |OPT|. For a maximisation problem, |A(x)| ≥ (1/α) · |OPT|.
In simple terms, the algorithm always finishes quickly and never does worse than α times the best possible answer.
NP-Complete
A language L that is both in NP (has a polynomial-time verifier) and is NP-Hard (every language in NP reduces to L in polynomial time).
Think of it as the "hardest" tier of NP: if you could solve any NP-Complete problem efficiently, you could solve all of NP efficiently.
Efficient verifier
A polynomial-time algorithm V that takes an input x and a certificate c and outputs accept or reject. The language it defines is the set of inputs for which there exists some certificate that makes V accept.
In simple terms, a verifier is a checker: given supposed evidence (the certificate), it quickly confirms or denies the claim.
Certificate (witness)
A piece of evidence supplied alongside an input to convince a verifier that the input belongs to the language. The certificate must be polynomial in the size of the input.
Think of it as a "proof" that can be checked quickly, even if finding it is hard.
Hamiltonian cycle
A cycle in a graph that visits every vertex exactly once and returns to the starting vertex.
In simple terms, a route through a graph that hits every node once before looping back.
P (polynomial time)
The class of decision problems solvable by a deterministic Turing machine in polynomial time.
NP (nondeterministic polynomial time)
The class of decision problems for which a "yes" answer can be verified in polynomial time given a suitable certificate.
The definition says: for every input x, |A(x)| ≤ 2 · |OPT(x)|. That is an upper bound, not an equality.
On some inputs the algorithm may return the exact optimum, so |A(x)| = |OPT(x)|.
On other inputs it may return exactly 2 · |OPT(x)|.
On yet others it could land anywhere in between.
The guarantee is a worst-case promise. It rules out the algorithm ever exceeding twice the optimal cost, but it does not force the algorithm to hit exactly twice optimal on any particular input.
Answer to Worksheet Q1: "some" inputs satisfy |A(x)| = 2|OPT|. The algorithm is permitted to be better than the worst case, and it is also permitted to hit the worst case, so neither "all" nor "no" is correct.
An efficient verifier V for a language L works as follows:
If x ∈ L, there exists at least one certificate c such that V(x, c) accepts.
If x ∉ L, then for every certificate c, V(x, c) rejects.
The critical subtlety is what happens when x ∈ L but you hand V the wrong certificate. The verifier is not obliged to accept every certificate for a valid input. It only needs to accept at least one.
So when x ∈ L: V accepts for some certificates and rejects for others. The verifier "sometimes" accepts.
Answer to Worksheet Q2: "sometimes." A valid input paired with the right certificate leads to acceptance; paired with a bad certificate, V may reject. The verifier is a checker, not a solver: it checks whether c is valid evidence, not whether x is in the language by itself.
The language L = {(G, C) : G is a graph and C is a Hamiltonian cycle in G} asks whether a given pair (graph, proposed cycle) satisfies the Hamiltonian property. This is a verification problem, not a search problem.
To decide membership, you only need to:
Check that C visits every vertex of G exactly once.
Check that every consecutive pair of vertices in C (including the last back to the first) is connected by an edge in G.
Both checks run in O(n + m) time, where n is the number of vertices and m is the number of edges. This is polynomial, so L ∈ P.
The key distinction: finding a Hamiltonian cycle is (believed to be) hard (the HamCycle decision problem is NP-Complete). Checking whether a given cycle is Hamiltonian is easy. This is precisely the P vs NP gap in action.
Answer to Worksheet Q3: True, L is in P. The input already contains both the graph and the proposed cycle, so the algorithm simply verifies the cycle in polynomial time.
Students often think a 2-approximation means the algorithm always returns exactly twice the optimal. It does not. The factor 2 is a worst-case ceiling, and the algorithm may do much better on many inputs.
Students confuse "x ∈ L so the verifier always accepts" with the correct statement "x ∈ L so there exists some certificate the verifier accepts." The verifier can reject bad certificates even for valid inputs.
Students mix up the HamCycle decision problem ("does G have a Hamiltonian cycle?", which is NP-Complete) with the verification problem ("is C a Hamiltonian cycle in G?", which is in P). The difference is whether the cycle is given to you or you must find it.
Students sometimes claim that because a problem is NP-Complete, nothing about it can be done in polynomial time. Verification of a certificate is polynomial for every NP problem. What is believed to be hard is finding the certificate.
⚠️ "Always / sometimes / never" and "all / some / no" questions appear frequently on exams. Read each quantifier with extreme care. The difference between "all" and "some" is the entire answer.
⚠️ The verifier question is a classic trap. Remember: the verifier's guarantee is existential (there exists a good certificate), not universal (all certificates work).
⚠️ Distinguishing search from verification is tested repeatedly. If the certificate is part of the input, the problem is a verification problem and likely in P. If you must find the certificate, the problem may be NP-Hard.
True or False: A 3-approximation algorithm for a minimisation problem always returns a solution of cost exactly 3 × OPT. _____
Fill in the blank: If L is NP-Complete and V is an efficient verifier for L, then for x ∈ L, V accepts for _____ certificates c.
True or False: The language {(G, C) : C is a Hamiltonian cycle in G} is NP-Complete. _____
True or False: Every problem in NP can be verified in polynomial time. _____
Fill in the blank: An α-approximation algorithm for a maximisation problem guarantees |A(x)| ≥ _____ · |OPT|.
Answers: 1. False (at most 3×, not exactly). 2. some (at least one, not all). 3. False (it is in P, since both G and C are given). 4. True (that is the definition of NP). 5. 1/α.
Q: A 2-approximation algorithm A for a minimisation problem is run on input x. Can |A(x)| ever be less than |OPT(x)|?
A: No. The algorithm returns a feasible solution, and no feasible solution can cost less than the optimum. The guarantee is OPT ≤ |A(x)| ≤ 2 · OPT.
Q: Suppose L is NP-Complete. You are given x ∈ L and a certificate c. Does V(x, c) necessarily accept?
A: No. The certificate c may be incorrect or malformed. The NP-Completeness guarantee says there exists at least one c that makes V accept, not that every c works.
Q: Is the problem "given a graph G, does G contain a Hamiltonian cycle?" in P?
A: This is not known. That problem (HamCycle) is NP-Complete. What is in P is the verification version: given both G and a proposed cycle C, checking whether C is a valid Hamiltonian cycle in G.
Q: Explain why verification of an NP-Complete problem is easier than solving it.
A: Verification receives the certificate as part of the input, so it only needs to check the solution, not search for one. Checking can be done in polynomial time for any problem in NP, by definition. Solving (finding the certificate) is what is believed to require super-polynomial time for NP-Complete problems.
This material connects directly to the search-to-decision reductions covered in the second half of the same worksheet. If you understand that verification is in P while search is (likely) hard, you have the intuition for why a decision oracle can be used to solve search problems incrementally.
The approximation-guarantee reasoning here also feeds into the approximation-algorithm proofs in Section 3 of the worksheet (MIS greedy algorithm, TSP inapproximability), where you need the same careful reading of what "α-approximation" promises.
More broadly, this sits within the P vs NP question, one of the central open problems in computer science and mathematics.
NP-Complete, NP-Hard, approximation algorithm, 2-approximation, minimisation problem, maximisation problem, efficient verifier, polynomial-time verifier, certificate, witness, Hamiltonian cycle, Hamiltonian path, P vs NP, complexity classes, decision problem, verification problem, EECS 376, foundations of computer science, University of Michigan, always sometimes never, all some no