NP-Completeness

Complexity analysis asks how many resources an algorithm uses. Complexity theory asks a broader question: which problems admit resource-efficient algorithms at all? NP-completeness identifies a large family of problems that are mutually connected by efficient transformations. A polynomial-time algorithm for any one NP-complete problem would imply polynomial-time algorithms for all of them; no such algorithm is known.

This does not prove that an NP-complete problem “cannot be solved.” Small and structured instances are solved every day. The classification says that an efficient exact algorithm for every instance would resolve the open question P = NP. Its engineering value is diagnostic: it redirects effort from an unsupported search for a general polynomial exact method toward explicit choices about instance size, structure, optimality, approximation, parameters, or heuristics.

Decision Problems

A decision problem has a yes-or-no answer. Complexity classes such as P and NP are conventionally defined for decision problems because yes/no languages provide a uniform mathematical model.

Formally, a language is a set L of finite bit strings. An encoded instance x is a yes-instance exactly when x in L; deciding the problem means deciding membership in L. Graphs, formulas, and integers are mathematical objects, but an algorithm receives encodings of them. Reasonable encodings differ by at most polynomial conversion cost, while a deliberately compressed numeric value can change what “polynomial in the input” means.

Examples:

• PATH: Does a path from s to t exist?
• SUBSET-SUM: Is there a subset whose sum equals target T?
• VERTEX-COVER: Does the graph have a vertex cover of size at most k?
• TSP-DECISION: Is there a tour of total weight at most B?

An instance is encoded as a finite bit string. Running time is measured in the length of that encoding, not merely in a numeric value appearing inside it. A target T written in binary occupies Theta(log T) bits.

Optimization Problems

An optimization problem asks for the best feasible value or solution:

• find a minimum vertex cover;
• find a cheapest travelling-salesperson tour;
• maximize satisfied clauses;
• find a largest clique.

The associated decision question introduces a threshold: “is there a feasible solution of value at most B?” for minimization, or at least B for maximization.

If an optimization algorithm is polynomial, the decision version is polynomial: optimize, then compare with the threshold. Frequently a decision oracle can also recover an optimum through polynomially many queries. This process is called self-reduction: solve one problem instance by asking an oracle about smaller or more constrained instances of the same problem. For SAT, ask whether the formula remains satisfiable with x_1=true; keep that value if yes and otherwise set it false, then repeat for each variable. At most one oracle query per variable recovers a satisfying assignment after the original yes answer. For integer TSP with bounded encoded weights, first binary-search the optimal threshold, then constrain or remove candidate edges through further decision queries to recover a tour. The formulations are not literally identical, but their computational difficulty is closely linked.

Complexity labels must name the formulation. An optimization problem is normally called NP-hard, while its decision counterpart may be NP-complete; membership in NP is defined for yes/no languages.

Polynomial Time

P is the class of decision problems solvable by a deterministic algorithm in time O(n^c) for some constant c, where n is encoded input length.

Examples include the following decision problems:

• does an array contain a given key?;
• is target vertex t reachable from source s?;
• in a graph with nonnegative encoded edge weights, is there an s-to-t path of weight at most B?;
• does the graph have a spanning tree of weight at most B?;
• is the maximum s-to-t flow at least B?;
• does a bipartite graph have a matching of size at least k?;
• do two strings have a common subsequence of length at least k?

The associated computational problems—sorting, constructing a shortest path or MST, finding a maximum flow or matching, and computing an LCS—also have polynomial-time algorithms. Strictly, P classifies their yes/no counterparts as languages.

Polynomial time is a theoretical robustness criterion, not a guarantee of practical speed. n^100 is polynomial and unusable; a well-pruned exponential algorithm can be fast on small instances. The distinction remains powerful because polynomials compose: a polynomial number of polynomial-time stages remains polynomial, while general exponential growth eventually overwhelms fixed polynomial improvements.

Efficient Verification

A verifier receives an instance x and a certificate y, then accepts or rejects. A decision problem belongs to NP if every yes-instance has a certificate of length polynomial in |x| that a deterministic polynomial-time verifier accepts, and no no-instance has an accepted certificate.

For the standard nonnegative-integer subset-sum variant, a certificate can be one Boolean per input element. The verifier checks the vector length, accumulates selected values without overflowing, and compares with the target.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool verify_subset_sum(const uint64_t values[], const bool chosen[], size_t n,
                       uint64_t target) {
    if ((n > 0U) && (values == NULL || chosen == NULL)) {
        return false;
    }

    uint64_t sum = 0U;
    for (size_t i = 0; i < n; ++i) {
        if (!chosen[i]) {
            continue;
        }
        if (values[i] > target - sum) {
            return false;
        }
        sum += values[i];
    }
    return sum == target;
}

The maintained condition sum <= target makes target - sum safe. Because every value is nonnegative, once a selected prefix would exceed the target, no later selected value could bring it back down; rejecting immediately is mathematically sound, not merely an overflow workaround. A signed-integer formulation that permits cancellation needs a polynomial-width arbitrary-precision accumulator: summing n signed 64-bit inputs can require 64 + ceil(log_2 n) magnitude bits. Rejecting only because one machine-width prefix overflows would not be a correct verifier for that language.

Verification includes certificate well-formedness. A Hamiltonian-cycle verifier must ensure every listed vertex is in range, appears exactly once, consecutive vertices are adjacent, and the final vertex connects back to the first. Checking only edge existence could accept a short repeated cycle.

Certificates

Typical certificates are:

Certificates characterize yes-instances. A short certificate that no Hamiltonian cycle exists is not known for arbitrary graphs; NP does not require efficiently verifiable no-certificates. The class co-NP contains complements of NP problems. Whether NP = co-NP is also open; a proof that P=NP would imply equality.

Every problem in P belongs to NP: the verifier can ignore the certificate, solve the instance, and accept exactly the yes-instances. Therefore:

Whether the inclusion is strict is the P versus NP problem.

Complexity Classes

The essential relationships are:

P:             polynomial-time solvable decision problems
NP:            polynomial-time verifiable yes-instances
NP-hard:       at least as hard as every problem in NP
NP-complete:   both in NP and NP-hard

An NP-hard problem need not be a decision problem or even belong to NP. Optimization TSP is NP-hard. Some undecidable problems are also NP-hard under suitable reductions. Calling every difficult problem “NP-complete” is therefore incorrect.

If any NP-complete problem lies in P, then P=NP. If P != NP, no NP-complete problem has a polynomial-time exact algorithm for all instances. As of this writing, neither equality nor inequality has been proved; course material and software documentation should not claim otherwise.

Polynomial Reductions

A polynomial-time many-one reduction from problem A to problem B, written:

is a polynomial-time computable transformation f satisfying:

After transformation, one answer to B determines the answer to A. Thus if B has a polynomial-time algorithm, so does A: compute f(x), run the B algorithm, return its answer.

Reduction Direction

To prove new problem B hard, reduce a known hard problem to B:

known-hard A  <=p  new B

The arrow follows the data transformation; hardness flows in the opposite explanatory direction: B can solve A, so B is at least as hard. Reducing B to a known NP-complete A proves that B is no harder than A; it does not establish NP-hardness.

Reduction Obligations

A complete reduction proves:

1. Construction: define f(x) for every valid instance.
2. Polynomial size/time: output representation and construction are polynomial in |x|.
3. Forward direction: if x is yes for A, then f(x) is yes for B.
4. Reverse direction: if f(x) is yes for B, then x is yes for A.

Checking only examples or one implication does not prove equivalence.

Worked Reduction

CLIQUE asks whether graph G=(V,E) contains at least k pairwise adjacent vertices. VERTEX-COVER asks whether a graph contains at most r vertices touching every edge.

To reduce CLIQUE to VERTEX-COVER:

1. Construct the complement graph G_bar: it has the same vertices, and distinct vertices are adjacent exactly when they are not adjacent in G.
2. Set r=|V|-k.
3. Ask whether G_bar has a vertex cover of size at most r.

The proof uses two equivalences.

• A set C is a vertex cover in any graph exactly when V-C is an independent set. If an uncovered edge existed inside V-C, independence would fail; conversely an edge with neither endpoint in C would be such an internal edge.
• A set is a clique in G exactly when it is independent in G_bar, by the definition of graph complement.

Therefore:

G has a clique of size at least k
iff G_bar has an independent set of size at least k
iff G_bar has a vertex cover of size at most |V|-k.

Constructing an adjacency matrix for the complement takes O(V^2) time and size, polynomial in the input. Since CLIQUE is NP-complete, this reduction proves VERTEX-COVER NP-hard; a polynomial verifier for a proposed cover proves it belongs to NP, hence it is NP-complete.

NP-Hardness

A problem B is NP-hard if every problem in NP reduces to it. In practice, transitivity makes it enough to reduce one known NP-complete problem:

Reductions compose. If A <=p B through f and B <=p C through g, then g(f(x)) reduces A to C; polynomial running times and output sizes remain polynomial under composition.

NP-hardness is a worst-case statement. It neither says every instance is hard nor predicts a particular solver’s performance distribution. A family may have easy random instances, hard phase-transition instances, and useful restricted cases.

NP-Completeness

To prove a decision problem B NP-complete:

1. Prove B is in NP by specifying a polynomial certificate verifier.
2. Choose a known NP-complete source problem A.
3. Construct a polynomial transformation from A to B.
4. Prove x is yes for A iff f(x) is yes for B.
5. Conclude B is NP-hard; combine with membership to conclude NP-complete.

Choose a source problem whose structure resembles the target:

• 3-SAT for local binary choices and logical constraints;
• CLIQUE or INDEPENDENT-SET for pairwise compatibility;
• VERTEX-COVER for selecting objects that touch every constraint;
• HAMILTONIAN-CYCLE for global sequencing;
• SUBSET-SUM for exact numeric selection.

Gadgets in a reduction represent variables, clauses, choices, or consistency. Each gadget needs two proofs: any source solution configures it into a target solution, and any target solution can be decoded into a consistent source solution.

Cook-Levin

The Cook–Levin theorem establishes that Boolean satisfiability (SAT) is NP-complete.

SAT belongs to NP because a truth assignment is a polynomial-size certificate, and evaluating the formula is polynomial. NP-hardness is proved by encoding the accepting computation of an arbitrary polynomial-time nondeterministic machine—or equivalently a polynomial verifier—into a Boolean formula.

The formula enforces a valid computation tableau:

• exactly one symbol occupies each tape cell at each time;
• exactly one machine state and head position occur at each time;
• the first row encodes the input and candidate certificate;
• adjacent rows obey the machine’s local transition rules;
• an accepting state appears by the polynomial time bound.

The formula is satisfiable exactly when some certificate makes the verifier accept. Because the tableau has polynomially many cells and local constraints, the formula size and construction time are polynomial. This provides the first NP-complete problem from the definition of NP rather than from a previously known hard problem.

Cook–Levin does not prove P != NP. It proves that SAT is representative of all NP verification: a polynomial SAT solver would imply P=NP.

Classic Problems

SAT

Input: a Boolean formula. Question: does any assignment satisfy it? General SAT is NP-complete by Cook–Levin.

3-SAT

Input: a conjunction of clauses, each with at most or exactly three literals under the selected convention. Question: does any assignment satisfy all clauses? 3-SAT is NP-complete. General SAT clauses can be transformed into bounded-width clauses with auxiliary variables while preserving satisfiability and polynomial size.

By contrast, 2-SAT is in P; implication graphs and strongly connected components solve it in linear time. Changing clause width from two to three crosses a genuine complexity boundary.

Clique

Input: undirected graph G and integer k. Question: is there a set of at least k mutually adjacent vertices? The certificate is the vertex set; verification checks O(k^2) pairs. CLIQUE is NP-complete.

Vertex Cover

Input: undirected graph G and integer k. Question: can at most k vertices touch every edge? The complement relationship with independent set and reductions from clique establish its central place among graph-selection problems.

Hamiltonian Cycle

Input: graph G. Question: is there a simple cycle visiting every vertex exactly once? Verification is polynomial; finding such a cycle is NP-complete.

Hamiltonian and Eulerian questions differ fundamentally. Eulerian circuits require every edge once and are characterized through degrees and connectivity in polynomial time. Hamiltonian cycles require every vertex once and encode global combinatorial choice.

Travelling Salesperson

TSP decision asks whether a weighted graph has a tour visiting every vertex and returning to the start with weight at most B. It is NP-complete. The optimization version is NP-hard.

Metric TSP, where weights satisfy triangle inequality, remains NP-hard but admits constant-factor approximation. Arbitrary weighted TSP without metric structure cannot have the same guarantee unless major complexity consequences follow.

Subset Sum

Input: nonnegative integers and target T. Question: does a subset sum exactly to T? A chosen-index certificate is easy to verify; the decision problem is NP-complete. Backtracking takes O(2^n) in the worst case, while target-indexed dynamic programming takes pseudo-polynomial time. Signed variants remain reducible to related formulations but need different state ranges and arithmetic contracts.

Pseudo-Polynomial Time

An algorithm polynomial in numeric value is not necessarily polynomial in encoded input length. The O(nT) subset-sum DP has T+1 states, but binary T uses only Theta(log T) bits. If T can be 2^n, the DP remains exponential in input length.

This explains why weakly NP-complete problems such as subset sum can have pseudo-polynomial algorithms. Strongly NP-hard problems remain hard even when numeric values are polynomially bounded; a pseudo-polynomial algorithm for such a problem would imply a polynomial algorithm under those bounds.

Pseudo-polynomial algorithms are often the best practical exact choice when capacities, budgets, or totals are naturally small. Complexity classification describes scaling under unrestricted encodings; engineering should also describe actual numeric regimes.

Exact Methods

NP-hardness does not eliminate exact algorithms. It changes expected worst-case scaling.

Backtracking

Backtracking builds a candidate incrementally and abandons a state as soon as no completion can be feasible. A state must record the choices already fixed, the choices still available, and enough derived information to test constraints cheaply. After a recursive call, every mutation must be undone before the next branch.

For SAT, choose an unassigned variable, try a truth value, simplify clauses, and backtrack if any clause becomes false. Unit propagation is stronger than waiting for a full assignment: when all but one literal in a clause are false, the final literal is forced. In

(x or y) and (not x or z) and (not y or not z)

trying x=true forces z=true; the third clause then forces y=false, producing a satisfying assignment without branching on the other two variables. Trying variables from the most constrained clauses often exposes contradictions earlier, but it does not change the exponential worst-case guarantee.

Memoization can merge repeated states only when the memoization key captures every fact that affects future feasibility. Caching merely the recursion depth in a SAT or Hamiltonian search would combine unrelated partial assignments and be unsound.

Branch-and-Bound

Optimization search adds two quantities:

• the incumbent, the best complete feasible solution found so far;
• an optimistic bound on every completion of a partial state.

For minimization, prune a state when its lower bound is at least the incumbent; for maximization, prune when its upper bound is no better. The inequality may be strict if every optimum must be enumerated rather than only one.

For a symmetric four-city TSP, let AB=2, AC=9, AD=10, BC=6, BD=4, and CD=3. Tour A-B-D-C-A costs 18, establishing an incumbent. For a partial route ending A-D, a valid lower bound is:

cost already paid                       10
minimum edge from D into {B,C}           3
MST cost connecting unvisited {B,C}      6
minimum edge from {B,C} back to A         2
total lower bound                        21

No completion of A-D can beat 18, so that whole branch is discarded. The bound is safe because every completion must enter the unvisited set, connect all of it, and return to A. A tighter bound costs more per node but can save an exponential number of descendants. Best-first search expands the smallest lower bound first and exposes an optimality gap naturally; depth-first search uses less memory and may find an incumbent sooner.

Meet-in-the-Middle

When a solution combines two nearly independent halves, enumerate each half and join the results. For subset sum:

split values into left and right halves
L = every (sum, subset-mask) from the left half
R = every (sum, subset-mask) from the right half
sort R by sum
for each (x,left-mask) in L:
    binary-search R for target-x
    if found, return the two masks
return no solution

For values [3,34,4,12,5,2] and target 9, the halves produce:

left  [3,34,4]: 0, 3, 34, 37, 4, 7, 38, 41
right [12,5,2]: 0, 12, 5, 17, 2, 14, 7, 19
sorted right:   0, 2, 5, 7, 12, 14, 17, 19

When the left sum is 4, binary search finds complement 5, recovering subset {4,5}. Left sum 7 also finds complement 2, recovering {3,4,2}. Keeping masks or parent records is essential if the solver must return a certificate rather than only true.

Each list has about 2^(n/2) entries. Straightforward enumeration and sorting take O(n 2^(n/2)) time and O(2^(n/2)) space, often written O*(2^(n/2)) when polynomial factors are suppressed. This remains exponential, but for n=50 it replaces roughly 2^50 full subsets with two lists near 2^25. Implementations must check sum arithmetic, memory-size multiplication, and whether a bit mask can represent half the variables. With nonnegative inputs, sums above the target may be discarded; that pruning is invalid for signed inputs because later negative values can reduce a sum.

Integer Programming

Integer programming expresses choices algebraically. A minimum vertex cover uses one binary variable x_v per vertex:

The constraint says each edge has a selected endpoint. If the binary restriction is temporarily relaxed to 0 <= x_v <= 1, linear programming gives a lower bound for branch-and-bound. Cutting planes add inequalities obeyed by all integer solutions but violated by the fractional relaxation. Presolve removes fixed or redundant variables; primal heuristics find incumbents; branching restores integrality. A mature solver combines these mechanisms and can return both a solution and a bound proving optimality or quantifying the remaining gap.

Solver Encodings

SAT represents every constraint with Boolean variables and clauses. Modern solvers use conflict-driven clause learning: after a contradiction, analyze the implication chain, add a clause that prevents the same conflicting combination, and backjump beyond irrelevant recent choices. Restarts change the search trajectory without forgetting learned clauses.

Satisfiability modulo theories (SMT) combines Boolean search with decision procedures for a theory such as linear integer arithmetic, real arithmetic, fixed-width bit vectors, arrays, or uninterpreted functions. Formula x>3 and y=x+2 and y<5 is propositionally consistent if its atoms are treated as unrelated Booleans, but an arithmetic theory proves it inconsistent. Choosing the theory determines the meaning and decidability boundary; “use SMT” is not a complete model specification.

Constraint programming works with finite-domain variables and propagators. An all_different constraint for scheduling or coloring can prune more strongly than a collection of pairwise inequalities. Symmetry-breaking rules—such as fixing the first color or ordering interchangeable machines—remove equivalent solutions without removing a genuinely distinct answer.

Exact algorithms should report both a feasible solution and, when possible, a certificate of optimality or exhaustion. Timeouts require an explicit status: “best known with bound” is not “proven optimal.”

Approximation

An approximation algorithm runs in polynomial time and guarantees a bound relative to optimum.

For minimization, an alpha-approximation returns cost at most alpha * OPT. For maximization, conventions commonly guarantee value at least OPT/alpha for alpha >= 1, or use a fraction rho * OPT.

Vertex-Cover Approximation

Repeatedly choose any uncovered edge (u,v), add both endpoints to the cover, and delete all incident edges.

C = empty
while an uncovered edge (u,v) remains:
    add u and v to C
    mark every edge incident to u or v covered
return C

Chosen edges share no endpoints, so they form a matching M. Every vertex cover must contain at least one endpoint of every edge in M, hence OPT >= |M|. The algorithm takes exactly two endpoints per chosen edge:

It is therefore a 2-approximation. The guarantee is worst-case and independent of input luck.

Approximation quality varies by problem and assumptions. Metric TSP admits constant-factor algorithms; general TSP behaves differently. An approximation claim must state its ratio, objective direction, and input conditions.

Parameterization

Parameterized complexity separates overall input size n from a parameter k expected to be small. A problem is fixed-parameter tractable (FPT) if it can be solved in:

time for any computable function f. Exponential dependence is confined to k rather than n.

For vertex cover parameterized by solution size k, choose an uncovered edge (u,v). Every valid cover contains u or v, so branch on those two choices and decrement k. The search tree has at most 2^k leaves, with polynomial work per node. This is practical when k is small even if n is large.

Kernelization preprocesses an instance into an equivalent one whose size is bounded by a function of k. A kernel plus bounded search can turn structural restrictions into reliable performance.

The statement “exponential” is incomplete without saying exponential in which parameter. Treewidth, number of colors, solution size, capacity, and edit distance can each expose useful tractable regimes.

Heuristics

A heuristic aims for useful solutions without a universal approximation ratio or an exhaustive proof of optimality. Its search rule can be precise even when its output guarantee is empirical.

Construction

A constructive heuristic starts empty and repeatedly makes a cheap local choice. Nearest-neighbor TSP goes to the closest unvisited city, while a scheduling heuristic may place the job causing the smallest immediate conflict. Construction is fast and supplies an incumbent, but early choices can force an expensive final connection. Randomized greedy construction chooses among several strong candidates instead of always taking the top one; repeated runs explore different basins.

Local Search

Local search defines a neighborhood of solutions and repeatedly moves to an improving neighbor. TSP’s 2-opt move removes two tour edges and reconnects the two path pieces in the other possible way. With points A=(0,0), B=(2,2), C=(0,2), D=(2,0), tour A-B-C-D-A has two crossing diagonal edges and length about 9.66. Replacing A-B and C-D with A-C and B-D produces A-C-B-D-A, the square perimeter of length 8.

A local optimum has no improving neighbor under the selected move; it need not be globally optimal. Larger neighborhoods such as 3-opt may escape more traps but cost more to search. Delta evaluation should compute only edges changed by a move rather than recomputing the entire objective.

Escaping Traps

Simulated annealing sometimes accepts a worsening move of cost increase Delta with probability:

At temperature T=2, a move worse by one is accepted with probability about 0.61; at T=0.1, the probability is about 0.000045. High temperature explores, while gradual cooling shifts toward improvement. A schedule that cools too quickly behaves like ordinary local search; one that cools too slowly spends the budget wandering.

Tabu search records recent moves or attributes and temporarily forbids them, preventing immediate cycling; aspiration rules allow a tabu move when it beats the best solution seen. Evolutionary methods maintain a population, then combine and mutate candidates, but representation matters: naive crossover between tours can duplicate cities and omit others. Learned branching or candidate scoring can guide any of these methods, yet prediction quality does not become a correctness proof.

Randomized restarts are a simple reliability tool. If one independent run finds a target-quality solution with probability p, then r runs all fail with probability (1-p)^r. Independence is an approximation when runs share preprocessing or similar starting states, so experiments should measure rather than assume it.

Evaluation

Evaluate heuristics against known optima on small instances and valid lower or upper bounds on larger ones. For a minimization problem with incumbent cost U and lower bound L, the absolute gap is U-L; a relative gap must state its denominator and its behavior near zero. Use representative and adversarial instance families, fixed time or operation budgets, disclosed random seeds, and several independent runs. Report median, dispersion, best solution, and bound—not only the best lucky run.

Hybrid methods are common: a heuristic quickly finds a strong incumbent, then branch-and-bound uses it to prune; an exact solver later proves optimality or returns the remaining gap at timeout. The heuristic improves speed, while the solver’s bound supplies the guarantee.

Practical Responses

When a required problem is NP-hard, make the trade-off explicit:

1. Restrict the input. DAGs, trees, planar graphs, bounded treewidth, small integer targets, or metric weights may admit better algorithms.
2. Choose a parameter. Use FPT methods when one structural quantity is small.
3. Use exact exponential search. Appropriate for small instances or when proof of optimality is mandatory.
4. Approximate with a guarantee. Appropriate when a known ratio satisfies the application.
5. Use heuristics with measurement. Appropriate when solution quality can be assessed empirically or bounded independently.
6. Relax the model. Change constraints or objectives with stakeholder agreement.
7. Use a mature solver. Encodings may outperform bespoke algorithms and provide certificates or gaps.

Record instance limits, timeout behavior, nondeterminism, numeric assumptions, and what guarantee is returned. “NP-hard” is not a reason to stop; it is a reason to stop promising all three of generality, exactness, and polynomial worst-case time simultaneously.

Reduction Errors

• Calling a problem NP-complete without proving both membership in NP and NP-hardness.
• Reducing the new problem to a known hard problem instead of the known hard problem to the new one.
• Proving only one direction of the yes-instance equivalence.
• Ignoring the time or size of the reduction construction.
• Treating a fast verifier as a fast solver.
• Saying NP means “non-polynomial”; it means nondeterministic polynomial time.
• Claiming NP-hardness proves no efficient algorithm exists; that conclusion is conditional on P != NP.
• Treating pseudo-polynomial time as polynomial in binary input length.
• Calling an optimization problem NP-complete without specifying a decision formulation.
• Reporting heuristic output as exact or approximately guaranteed without a proof.

NP Review

• P contains polynomial-time solvable decision problems; NP contains problems with polynomially verifiable yes-certificates.
• P is contained in NP; whether equality holds remains open.
• A polynomial reduction preserves yes/no answers and transfers algorithmic solvability from target back to source.
• NP-hard problems are at least as hard as every problem in NP; NP-complete problems are NP-hard members of NP.
• Cook–Levin proves SAT NP-complete by encoding polynomial verification as satisfiability.
• SAT, 3-SAT, clique, vertex cover, Hamiltonian cycle, TSP decision, and subset sum are canonical NP-complete problems.
• Pseudo-polynomial, exact exponential, approximation, parameterized, restricted, and heuristic methods address different practical requirements.
• Complexity classification is a worst-case guide; it must be paired with the actual instance distribution, constraints, guarantees, and resource budget.

NP Problems

Complexity Vocabulary

1. Define P, NP, NP-hard, and NP-complete without using the word “hard” as the entire definition.
2. Distinguish decision, search, and optimization versions of TSP.
3. Explain why P is a subset of NP.
4. State the four proof obligations of a polynomial reduction.

Verification

5. Specify certificates and polynomial verifiers for 3-coloring, clique, vertex cover, Hamiltonian cycle, and TSP decision.
6. Redesign verify_subset_sum with an enum that distinguishes invalid input, rejection, and acceptance. Explain why its nonnegative sum <= target invariant makes arithmetic overflow unreachable; then state the wider-arithmetic contract needed for a signed-input verifier.
7. Write a C17 verifier for a Hamiltonian-cycle certificate using an adjacency matrix.

Reductions

8. Prove that a set is independent exactly when its complement is a vertex cover.
9. Complete the CLIQUE-to-VERTEX-COVER reduction with boundary cases k<0, k>|V|, self-loops, and the selected simple-graph convention.
10. Reduce INDEPENDENT-SET to CLIQUE using graph complementation.
11. Reduce HAMILTONIAN-CYCLE to TSP decision by assigning weights to edges and nonedges in a complete graph.

Proof Auditing

12. A proof maps new problem B to known NP-complete problem A and concludes B is NP-hard. Identify the invalid inference and state what the mapping does prove.
13. A proposed reduction proves x in A implies f(x) in B but omits the reverse. Construct a transformation satisfying that one implication while carrying no useful equivalence.
14. Explain why showing an exponential brute-force algorithm does not prove NP-hardness.

Exact Algorithms

15. Implement meet-in-the-middle subset sum and compare it with 2^n backtracking on equal inputs.
16. Write branch-and-bound for TSP using a safe lower bound. Report incumbent, lower bound, and optimality gap at timeout.
17. Derive the O(2^k * poly(n)) branching algorithm for parameterized vertex cover and prove completeness.

Approximation

18. Implement the 2-approximation for vertex cover and verify its output is a cover.
19. Construct a graph where that algorithm returns a cover twice the optimum size.
20. Compare an approximation guarantee with empirical average quality; explain why neither replaces the other.

Hardness Decisions

21. Choose a practical approach for examination timetabling, delivery routing, and dependency-aware project selection. State which requirement—generality, exactness, guarantee, or runtime—you relax in each.
22. Design an experimental protocol for a heuristic TSP solver using lower bounds, reproducible seeds, time budgets, and several instance families.

Complexity Consequences

23. Explain how a polynomial algorithm for any one NP-complete problem yields polynomial algorithms for every problem in NP through reduction composition.
24. Research one restricted family in which an NP-complete graph problem becomes polynomial. State the restriction, algorithm, and why the general hardness proof no longer applies unchanged.