NP-Complete Problems, in depth: the core catalogue, certificates, weak versus strong hardness, choosing a reduction source, the 3-SAT phase transition and a SAT-solved scheduling example

What being on the list means

Membership on the list means two concrete things, and you should be able to say both for any problem you call NP-complete. The first is a certificate: a short piece of evidence that a yes-answer is correct, checkable in polynomial time. For Vertex Cover it is the set of chosen vertices; checking it means scanning every edge once. The second is a reduction from a problem already known to be NP-complete: a polynomial-time translation that maps yes-instances to yes-instances and no-instances to no-instances. A certificate without a reduction only puts the problem in NP. A reduction without a certificate only makes it NP-hard.

The list begins with Cook and Levin, who independently showed in 1971 to 1973 that Boolean satisfiability is NP-complete. In 1972 Karp showed 21 problems NP-complete by chains of reductions starting from SAT, and Garey and Johnson's 1979 book catalogued about 300. Their book also fixed six problems as the standard starting points for new proofs: 3-SAT, 3-Dimensional Matching, Vertex Cover, Clique, Hamiltonian Cycle and Partition. Almost every hardness proof you will read descends from one of them, as the tree below shows.

A reference card for the core problems

The table is a reference card. Weak means the problem is hard only when its numbers are exponentially large, so a pseudo-polynomial dynamic programme solves it when the numbers are small. Strong means it stays hard even with numbers written in unary. The last column gives the best polynomial-time guarantee known, together with the matching hardness result where one is established.

Two rows deserve emphasis. Partition and Knapsack are hard only because their numbers can be huge. Your capacity planner with integer gigabytes up to 10,000 is therefore genuinely solvable by dynamic programming. Bin Packing is strongly hard because it encodes 3-Partition, so no such escape exists for it, and approximation is the realistic goal. Approximation proofs for the middle rows are worked through in Approximation Algorithms, in depth.

Choosing a source problem for your own proof

When you suspect that a problem at work is NP-complete, a proof sharpens the suspicion into a design decision. Most of the effort lies in picking the right source problem, and the reliable heuristic is to match the shape of your problem's choices:

• Choose a subset under pairwise conflicts, such as jobs that cannot share a slot or features that exclude each other: reduce from Independent Set or Vertex Cover.
• Cover every requirement with few resources, such as tests covering code paths or regions covered by servers: reduce from Set Cover or Vertex Cover.
• Assign one of k labels so that neighbours differ, such as frequencies, registers or time windows: reduce from 3-Colouring.
• Order every item exactly once, such as routes, tours or pipelines that visit every stage: reduce from Hamiltonian Cycle.
• Split numbers into groups with equal or bounded sums, such as load balancing or packing: reduce from Partition for weak hardness and 3-Partition for strong.
• Arbitrary Boolean constraints, such as configuration or dependency resolution: reduce from 3-SAT directly. Each variable becomes a choice gadget and each clause a checking gadget.

The full reduction from 3-SAT to Clique, with both directions proved and tested, is in Clique NP-Hardness Reduction, in depth. Three errors recur in home-grown proofs. The first is reducing in the wrong direction, from your problem to SAT, which shows only that your problem is no harder than SAT. The second is proving only that a yes maps to a yes. The third is building a translation that is exponential in disguise, for example by writing numbers in unary when the source problem is only weakly hard.

Where instances get hard: the phase transition

NP-completeness is a statement about the worst case. Most instances you meet are far easier, and the easy and hard ones can be told apart. The clearest demonstration is random 3-SAT. Draw m clauses of three random literals over n variables. When the ratio m/n is small, almost every formula is satisfiable and a solver finds a solution almost at once. When it is large, almost every formula is unsatisfiable and contradictions surface quickly. Experiments by Mitchell, Selman and Levesque in 1992, and many since, put the crossover near m/n ≈ 4.26 and found that solver effort peaks sharply there. The exact threshold for 3-SAT is an empirical estimate and has not been proved. The experiment below reproduces the effect with a plain DPLL solver:

import random

def random_3sat(n, m, rng):
    clauses = []
    for _ in range(m):
        vs = rng.sample(range(1, n + 1), 3)
        clauses.append([v if rng.random() < 0.5 else -v for v in vs])
    return clauses

def dpll(clauses, assign, stats):
    while True:                                   # unit propagation
        unit, simplified = None, []
        for cl in clauses:
            if any(assign.get(abs(l)) == (l > 0) for l in cl):
                continue                          # clause already satisfied
            rest = [l for l in cl if abs(l) not in assign]
            if not rest:
                return False                      # conflict
            if len(rest) == 1:
                unit = rest[0]
            simplified.append(rest)
        clauses = simplified
        if unit is None:
            break
        assign[abs(unit)] = unit > 0
    if not clauses:
        return True
    stats["decisions"] += 1
    var = abs(clauses[0][0])
    for value in (True, False):
        trial = dict(assign)
        trial[var] = value
        if dpll(clauses, trial, stats):
            return True
    return False

rng, n, trials = random.Random(7), 50, 40
for ratio in (3.0, 3.5, 4.0, 4.26, 4.5, 5.0, 6.0):
    sat, work = 0, []
    for _ in range(trials):
        stats = {"decisions": 0}
        sat += dpll(random_3sat(n, int(ratio * n), rng), {}, stats)
        work.append(stats["decisions"])
    print(f"m/n={ratio:4.2f}  P(sat)={sat / trials:.2f}  "
          f"median decisions={sorted(work)[trials // 2]}")

At n = 50 the transition is blurred, but the shape is unmistakable. The share of satisfiable formulas falls steeply through the 4 to 4.5 band. One run gave 0.88 at 4.0, 0.53 at 4.26 and 0.30 at 4.5, and the median number of decisions peaked at 4.26. Raise n and the band narrows while the peak grows. The lesson: loosely and tightly constrained instances are both easy. The expensive ones are only just feasible or only just infeasible, which is what a capacity plan at 99 percent utilisation looks like.

Worked example: deployment windows as graph colouring

Here is a real-shaped task. Nine services must each be deployed in one of three maintenance windows. Two services conflict when they share a database or an on-call team, and conflicting services may not share a window. This is graph 3-colouring, which is NP-complete, but an instance of this size is trivial for a SAT solver. Industrial instances with tens of thousands of services usually are too. The encoding uses one Boolean variable per (service, window) pair and three clause families:

from itertools import combinations
from pysat.solvers import Glucose3          # pip install python-sat

def colouring_cnf(nodes, edges, k):
    pairs = [(v, c) for v in nodes for c in range(k)]
    var = {pair: i + 1 for i, pair in enumerate(pairs)}
    cnf = []
    for v in nodes:
        cnf.append([var[v, c] for c in range(k)])        # at least one window
        for c1, c2 in combinations(range(k), 2):
            cnf.append([-var[v, c1], -var[v, c2]])       # at most one window
    for u, v in edges:
        for c in range(k):
            cnf.append([-var[u, c], -var[v, c]])         # conflicts differ
    return var, cnf

def schedule(nodes, edges, k, pinned=()):
    var, cnf = colouring_cnf(nodes, edges, k)
    with Glucose3(bootstrap_with=cnf) as solver:
        assumptions = [var[v, c] for v, c in pinned]
        if not solver.solve(assumptions=assumptions):
            return None, solver.get_core()               # pins that clash
        model = {lit for lit in solver.get_model() if lit > 0}
    return {v: c for (v, c), i in var.items() if i in model}, None

nodes = ["auth", "billing", "ledger", "api", "web",
         "search", "index", "reports", "notify"]
edges = [("auth", "billing"), ("billing", "ledger"), ("ledger", "auth"),
         ("auth", "api"), ("billing", "api"), ("api", "web"),
         ("web", "search"), ("search", "index"), ("index", "reports"),
         ("reports", "ledger"), ("notify", "web"), ("notify", "api")]
# auth, billing and ledger form a triangle: pin them to break symmetry.
plan, core = schedule(nodes, edges, 3,
                      pinned=[("auth", 0), ("billing", 1), ("ledger", 2)])
print(plan or core)

The solver returns a valid plan, for example api in window 2, web in 0 and search in 1. Two details matter in practice. First, pinning a known clique breaks symmetry. Every colouring has k! relabelled twins, and on unsatisfiable instances an unpinned solver can waste time proving each twin infeasible. Second, passing pins as assumptions rather than unit clauses means that a failure returns an explanation. Add the conflict (api, ledger) and api now touches all three pinned services, so no window remains. Calling get_core() then returns the pinned literals that clash, here the three triangle pins, which tells the operator that api cannot join that triangle without a fourth window. The same pattern, with weights, moves to integer programming when the objective is a cost rather than feasibility. Integer Programming and LP, in depth shows how to model that, and SAT Solving, in depth explains what the solver is doing inside.

Failure modes

• Calling a problem NP-complete because it feels hard. Bipartite matching, shortest paths, 2-SAT, minimum cut and linear programming all have polynomial algorithms. Search for a reduction from your problem to one of them before giving up on exactness.
• Ignoring the weak/strong distinction. Ruling out exact Knapsack for a budget in whole dollars up to 50,000 would miss an O(n·T) table that runs in well under a second.
• Trusting a heuristic without a bound. Local search returns good answers on typical days and bad ones on unusual days. Without an LP relaxation or a known lower bound you cannot tell which kind of day it is.
• Benchmarking on easy instances. Randomly generated tests often sit far from the phase transition. Include near-capacity cases, because production reaches them during peaks.
• Exact solvers without time limits. Exponential worst cases do occur. Every solver call needs a deadline, plus a fallback to the best incumbent or a greedy answer.
• Naive TSP for small n. Brute force over n! orders stops at about 12 cities. Held-Karp dynamic programming, described in TSP via Dynamic Programming, reaches the low twenties.

Trade-offs

Every response to NP-completeness gives something up. Exact solvers such as SAT, CP and ILP give optimal or proven-infeasible answers on most structured instances, but their running time is unpredictable and they need modelling skill. Pseudo-polynomial dynamic programmes are exact and predictable, but only while the numbers stay small. Fixed-parameter algorithms such as O(2^k·n) branching for Vertex Cover are exact and fast when the answer k is small, and useless when it is not. Approximation algorithms guarantee a factor and run fast, but the factor may be too loose for a costly resource. Heuristics and metaheuristics are flexible and often excellent, but they give no guarantee at all. A sound production design layers them: greedy fallback, deadline-bounded exact solve, and a reported lower bound.

What to do next

1. For your current hard problem, write down the decision version and its certificate in one sentence each.
2. Match its shape to a row of the reference table and check whether your instances fall into a weak, small-parameter or special-structure case.
3. If you need a proof, reduce from the nearest problem in the family tree, and prove both directions.
4. Prototype an encoding in python-sat or an ILP solver, break obvious symmetries, and run it with a time limit.
5. Build a benchmark that includes near-threshold instances, not only random easy ones.
6. Ship the layered design: greedy fallback, deadline-bounded exact solve, and a reported optimality gap.