Computational Limits and Reductions
Prerequisites: S1 proofs and graphs; S2 complexity and search. Budget: 20-30 hours including reading and the solver. Outcome: distinguish an impossible general guarantee from an expensive finite problem, and prove a reduction in the useful direction.
Diagnostic
Explain why testing 100 inputs does not prove an algorithm correct for all inputs. Compare n squared with 2 to the power n as n grows. If either explanation is missing, revisit the proof and analysis worked examples before starting.
The mechanism
A decision problem asks a yes/no question about an encoded instance. An algorithm decides it if it terminates with the correct answer on every valid instance. A verifier instead checks a supplied witness. For a graph, a proposed k-clique can be checked by examining every pair among its k vertices. Efficient verification does not automatically give an efficient way to find that witness.
In a polynomial-time reduction from problem A to problem B, transform each A instance into a B instance so the yes/no answer is preserved. An efficient B solver would then solve A efficiently. To argue that B inherits A's hardness, reduce A to B. Reducing B to an easy problem establishes an upper bound instead. NP-hardness does not establish that every instance is difficult, or resolve whether P equals NP.
Undecidability concerns a different limit. If a total procedure H could decide whether any program halts on any input, construct D(p) to loop when H predicts that p(p) halts, and halt otherwise. Applying D to its own description contradicts H either way. This argument concerns unrestricted programs and a total, always-correct procedure; bounded execution remains a useful engineering tool.
Worked reduction: independent set to vertex cover
Let G have vertex set V. A subset S is independent exactly when its complement V minus S is a vertex cover. If an edge had both endpoints in S, S would not be independent and the complement would fail to cover that edge. Conversely, if the complement covers every edge, no edge can have both endpoints in S.
Thus G has an independent set of size at least k exactly when it has a vertex cover of size at most the size of V minus k. The graph is unchanged and the threshold conversion is inexpensive.
For path A-B-C, S={A,C} is independent and its complement {B} covers both edges. Choosing {A,B} fails independence; its complement {C} leaves A-B uncovered. The negative example matters as much as the positive one.
Guided assignment
Implement exhaustive independent-set and vertex-cover solvers for simple undirected graphs with at most 12 vertices. Represent a subset by a bit mask. For each graph and threshold k, compare the two decisions through the reduction. Include empty graphs, complete graphs, isolated vertices, and the path example. Record the number of subsets examined rather than presenting tiny runtimes as a scalability claim.
Then add a branch-and-bound pruning rule. Explain why it cannot discard an optimum. Compare exact results with the baseline on all graphs you can feasibly enumerate at a small vertex limit, plus seeded larger samples. Clearly state the tested bounds.
Acceptance: both directions of the reduction are written; exhaustive solvers agree after threshold conversion; the pruning rule has a correctness argument; exponential worst-case behavior remains explicit. A “fast on my sample” result is not a proof of polynomial complexity.
Independent transfer
Show that a clique in G is an independent set in the complement graph, defining the complement without self-loops. Then explain why a timeout in your exact solver means “unknown,” not “no.” Check: the witness pair condition reverses edge presence; a partial search has not excluded all remaining candidates.
Reading and defense
Use the NP-completeness and reductions sections of Introduction to Algorithms and the intractability material in The Algorithm Design Manual. Read for the proof structure, then reconstruct it without the source.
Defend why your reduction direction supports the claim you make. If you confuse direction or call timeout a negative result, redo the transfer with a new graph before passing the rubric.