14.2 Supplement: NP-Completeness and Reductions

Prerequisites: Complexity Analysis and Greedy Algorithms. This section does not attempt to prove whether P equals NP, but instead establishes four complexity classes, reduction directions, and practical engineering strategies for tackling NP-hard optimization problems.

What Is the Traveling Salesman Problem?

Consider general TSP instances with a variable number of cities and non-negative integer distances encoded in binary. "Finding the shortest tour" is an optimization problem; "does a tour exist with total length no more than K?" is a decision problem. The two are closely related, but their complexity labels must not be conflated:

• The decision version of TSP is NP-complete;
• The optimization version of TSP is NP-hard, and is typically not called NP-complete, because NP is defined in terms of decision problems.

The same story often appears in four forms: decision, search, counting, and optimization. Before discussing complexity, it's essential to clearly specify the input, output, and problem variant, otherwise, a statement like "this problem is NP-complete" might be referring to the wrong version entirely.

P, NP, NP-complete, and NP-hard

P is the set of decision problems that can be solved by a deterministic algorithm in polynomial time. In NP, every yes-instance has a certificate of polynomially bounded length that a deterministic algorithm can verify in polynomial time; no no-instance has an accepted certificate. P is contained in NP, and whether P equals NP remains open. Input size means the length of a finite encoding; an arbitrary-precision real number is not a free input unit.

A decision problem B is NP-complete if it satisfies both:

1. B is in NP;
2. Every problem in NP can be polynomial-time reduced to B.

NP-hard only requires that a problem be at least as difficult as the hardest problems in NP, in terms of reduction. It may be an optimization problem, may not belong to NP, and may even be undecidable. Thus, NP-complete is the intersection of NP and NP-hard, not a synonym for "any problem that runs slowly."

The fact that "no polynomial-time algorithm is known" does not prove a problem is NP-hard. A rigorous conclusion requires either a known theorem or a formal reduction proof.

Reduction Direction Cannot Be Reversed

Notated as:

A <=p B

For decision problems, this lesson uses polynomial-time many-one reductions: transform any A-instance into one B-instance while preserving the yes/no answer. If problem B has a polynomial-time algorithm, then so does problem A.

To prove that a new problem B is NP-hard, you must reduce a known NP-hard problem A to B. Reducing B to A only shows that B is not harder than A, it does not establish a lower bound on B's complexity.

The reduction must also preserve the answer:

The answer "yes" to an A instance  <=>  the answer "yes" to the transformed B instance

Simply stating that "the two problems look similar" is insufficient.

Heuristics and Bounded Approximations Are Not the Same

The nearest-neighbor TSP algorithm moves to the closest unvisited city. Its matrix must be square with non-negative integer entries and a zero diagonal. Asymmetry is allowed, and the triangle inequality is not required. start is an integer city index. An empty matrix accepts only the default start 0 and returns ([], 0); one city returns ([0, 0], 0). It is a heuristic: it provides no fixed approximation ratio guarantee for general distance matrices. The function must still validate input contracts, and it's wrong to infer global optimality from a single example route.

def tsp_nearest_neighbor(distance, start=0):
    city_count = len(distance)
    if not isinstance(start, int):
        raise TypeError("start must be an integer")
    if city_count == 0:
        if start != 0:
            raise IndexError("empty matrix requires the default start")
        return [], 0
    if not 0 <= start < city_count:
        raise IndexError("start city is out of range")
    if any(len(row) != city_count for row in distance):
        raise ValueError("distance matrix must be square")
    if any(not isinstance(value, int) or value < 0
           for row in distance for value in row):
        raise ValueError("distances must be non-negative integers")
    if any(distance[city][city] != 0 for city in range(city_count)):
        raise ValueError("diagonal distances must be zero")

    unvisited = set(range(city_count))
    unvisited.remove(start)
    route = [start]
    total = 0
    current = start

    while unvisited:
        next_city = min(
            unvisited,
            key=lambda city: (distance[current][city], city),
        )
        total += distance[current][next_city]
        route.append(next_city)
        unvisited.remove(next_city)
        current = next_city

    total += distance[current][start]
    route.append(start)
    return route, total

sample = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
assert tsp_nearest_neighbor(sample) == ([0, 1, 3, 2, 0], 80)

The result of 80 happens to be the optimal value for this small example, but this does not constitute a general guarantee for the nearest-neighbor algorithm. Evaluate a heuristic with benchmark instances, a runtime budget, and solution quality. For [[0,1,2],[1,0,100],[2,1,0]], starting at 0 yields 0→1→2→0 at cost 103, while 0→2→1→0 costs 4. Increasing 100 widens the gap. This counterexample uses the asymmetric distances allowed by the contract. Including matrix validation, time is Θ(n²) and extra space is O(n). City indices break distance ties, and input is unchanged.

Vertex Cover 2-Approximation

An unweighted undirected graph vertex cover requires selecting a set of vertices such that every edge has at least one endpoint in the set. The algorithm repeatedly picks an uncovered edge and adds both of its endpoints to the result, equivalent to constructing a maximal matching and selecting all its endpoints. Maximal means no edge can be added; maximum means the largest possible number of matching edges. This algorithm does not need a maximum matching. Input is an adjacency mapping with re-iterable neighbor collections and vertices whose hashing and equality are stable and reflexive. Every adjacency record denotes an undirected edge: duplicates collapse, one-sided records and missing keys for neighbor-only vertices are allowed, and self-loops raise ValueError.

def approx_vertex_cover(graph):
    edges = set()
    for vertex, neighbors in graph.items():
        for neighbor in neighbors:
            if neighbor == vertex:
                raise ValueError("self-loops are not supported")
            edges.add(frozenset((vertex, neighbor)))

    selected = set()
    for edge in edges:
        left, right = tuple(edge)
        if left not in selected and right not in selected:
            selected.update((left, right))
    return selected

def is_vertex_cover(graph, selected):
    return all(
        vertex in selected or neighbor in selected
        for vertex, neighbors in graph.items()
        for neighbor in neighbors
    )

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2],
}
cover = approx_vertex_cover(graph)
assert is_vertex_cover(graph, cover)

Each edge in the matching requires any vertex cover to include at least one of its endpoints, so the optimal solution size must be at least the number of matching edges. The algorithm selects two endpoints for each matching edge, resulting in a solution no more than twice the optimal size. The proof bounds the number of vertices in an unweighted problem; it does not directly apply to vertex weights. The implementation collects edges, then scans them once. For V input vertices, R adjacency records, and E distinct edges, expected time is O(V+R) and extra space is O(V+E), assuming constant-time hashing. Set iteration order may change the matching but preserves the factor-2 guarantee.

How to Choose When Facing NP-hard Problems

Scenario	Methods to Consider	Must Clarify
Instances are small	Enumeration, branch and bound, pruning	May still enumerate exponentially or factorially many candidates
An optimal solution is required	Solvers like ILP/SAT/CP or specialized exact algorithms	Timeout behavior and optimality certificates
A near-optimal solution is acceptable	Proven approximation algorithms	Approximation ratio and applicable conditions
Data has small parameters	Parameterized algorithms	Exponential component's dependence on which parameter
A feasible solution is sufficient	Heuristics, local search, metaheuristics	No optimality guarantees
Instances have special structures	Use treewidth, planarity, or domain-specific constraints	Whether the structure holds universally

NP-hard does not mean all instances are difficult. Real-world data may be small or possess additional structure; solvers often handle instances of substantial size. NP-hardness does not unconditionally prove that a problem requires exponential time. Assuming P≠NP, it rules out a polynomial-time exact algorithm for the general case. These results do not replace measurements of actual instance distributions.

Check Reductions and Guarantees

1. Explain in your own words why "A is known to be hard, and B ≤_p A" does not prove that B is hard.
2. Express the vertex cover and independent set complement relationship as a bidirectional yes/no proof.
3. Perform a brute-force enumeration of the TSP for 6 cities and compare it to the result of the nearest neighbor heuristic, actively seeking counterexamples.
4. Derive the 2-approximation upper and lower bounds for vertex cover using a maximal matching.
5. For an optimization problem, write both its decision version and a certificate verifier.

Distinguish Hardness from Solver Guarantees

NP-completeness provides a verifiable classification method, not comfort for "code that can't be written." First, fix the problem version and examine class membership and reduction directions; once engineering decisions are made, distinguish among three different commitments: exact, approximate, and heuristic.

The next section shifts perspective: Amortized Analysis does not assess how difficult a problem itself is, but rather how occasionally expensive operations are absorbed into the overall cost.