NP-Completeness & Reductions

To reason precisely about hardness, we restrict attention to decision problems: problems with a yes/no answer. 'Is there a Hamiltonian cycle in this graph?' rather than 'Find a Hamiltonian cycle.' This restriction is minor — an algorithm for the search version gives a decision algorithm, and vice versa with one extra query — but it makes the theory clean.

The class P contains every decision problem solvable by a deterministic algorithm in time O(n^k) for some constant k, where n is the input size. 'Polynomial time' is the formal stand-in for 'feasible': an O(n^100) algorithm is technically in P but impractical, yet in practice polynomial algorithms are almost always fast. Crucially, polynomial time is closed under composition: calling a polynomial-time subroutine a polynomial number of times stays polynomial.

Examples in P: sorting, shortest paths (Dijkstra), primality testing (AKS algorithm, 2002 — a surprise!), bipartite matching, linear programming, 2-SAT, 2-coloring.

The input encoding matters. An integer n given in binary has input length ⌊log₂ n⌋ + 1 bits. An algorithm that runs in O(n) steps on the numeric value n is actually exponential in the input length. This distinction — unary vs binary representation — is why 'pseudo-polynomial' algorithms like dynamic programming for the 0/1 Knapsack are not truly polynomial.

# 2-SAT in O(n + m) — a problem in P
# Encode clause (a OR b) as two implications: NOT a -> b, NOT b -> a
# Build implication graph, find SCCs (Kosaraju/Tarjan), check no variable
# and its negation are in the same SCC.

def two_sat(n_vars, clauses):
    """n_vars: number of Boolean variables (0..n_vars-1).
    clauses: list of (a, b) where a,b in {0..2n-1};
             literal x = 2x (positive), 2x+1 (negative)."""
    N = 2 * n_vars
    adj  = [[] for _ in range(N)]
    radj = [[] for _ in range(N)]

    def add_impl(u, v):          # u -> v
        adj[u].append(v)
        radj[v].append(u)

    def neg(x): return x ^ 1    # flip last bit

    for a, b in clauses:         # (a OR b) = (NOT a -> b) AND (NOT b -> a)
        add_impl(neg(a), b)
        add_impl(neg(b), a)

    # Kosaraju SCC
    order, visited, comp = [], [False]*N, [-1]*N
    def dfs1(v):
        visited[v] = True
        for u in adj[v]:
            if not visited[u]: dfs1(u)
        order.append(v)
    def dfs2(v, c):
        comp[v] = c
        for u in radj[v]:
            if comp[u] < 0: dfs2(u, c)
    for v in range(N):
        if not visited[v]: dfs1(v)
    c = 0
    for v in reversed(order):
        if comp[v] < 0: dfs2(v, c); c += 1

    for x in range(n_vars):
        if comp[2*x] == comp[2*x+1]:
            return None          # UNSAT
    # Assign: variable x is True iff its positive literal has higher SCC topo order
    assignment = [comp[2*x] > comp[2*x+1] for x in range(n_vars)]
    return assignment

NP stands for Nondeterministic Polynomial time. There are two equivalent definitions, and understanding both is important.

Definition 1 (verifier). A problem L is in NP if there exists a polynomial-time algorithm V(x, c) such that: for every yes-instance x, there exists a certificate (witness) c with |c| = poly(|x|) where V(x, c) = YES; and for every no-instance x, no certificate makes V accept. Intuitively, NP = problems where correct answers can be checked efficiently, even if finding them might be hard.

Definition 2 (nondeterministic TM). A problem is in NP if a nondeterministic Turing machine can solve it in polynomial time — meaning there exists some computation path that accepts in poly time for yes-instances, and all paths reject for no-instances. Nondeterminism is like a machine that guesses the certificate optimally.

These definitions are provably equivalent. The first is more intuitive for most purposes.

Examples. HAMPATH (does a Hamiltonian path exist?): certificate = the path itself; verify in O(n). CLIQUE (does G have a k-clique?): certificate = the k vertices; verify all O(k²) edges exist. SAT: certificate = the satisfying assignment; evaluate the formula in O(n).

The key asymmetry. For no-instances in NP, we require that no certificate works — but we need no witness of infeasibility. The class co-NP captures problems where no-instances have short certificates (e.g., UNSAT ∈ co-NP if we could provide short proofs of unsatisfiability — but we don't know if co-NP = NP).

Clearly P ⊆ NP: if you can solve a problem in polynomial time, you can verify a solution in polynomial time (just ignore the certificate and re-solve). Whether P = NP is the million-dollar question.

# NP certificate verification for 3-SAT
# (This is NOT a solver — it's the verifier V(x, c))

def verify_3sat(clauses, assignment):
    """
    clauses: list of 3-tuples of integers.
             literal k > 0 means variable k is True;
             literal k < 0 means variable |k| is False.
    assignment: dict {var: True/False}
    Returns True iff the assignment satisfies all clauses.
    """
    for clause in clauses:
        satisfied = False
        for lit in clause:
            var = abs(lit)
            val = assignment[var]
            if (lit > 0 and val) or (lit < 0 and not val):
                satisfied = True
                break
        if not satisfied:
            return False
    return True

# Example: (x1 OR NOT x2 OR x3) AND (NOT x1 OR x2 OR x3)
clauses = [(1, -2, 3), (-1, 2, 3)]
assignment = {1: True, 2: False, 3: True}
print(verify_3sat(clauses, assignment))  # True — polynomial-time check

A polynomial-time (many-one) reduction from problem A to problem B, written A ≤_p B, is a function f computable in polynomial time such that: x ∈ A if and only if f(x) ∈ B. In words: any instance of A can be translated into an instance of B in polynomial time, such that yes-instances map to yes-instances and no-instances map to no-instances.

Why this is powerful. If A ≤_p B and B ∈ P, then A ∈ P — solve A by first reducing to B and then running B's algorithm. Equivalently (contrapositive): if A ∉ P (A is hard) and A ≤_p B, then B ∉ P (B is at least as hard). This is the mechanism by which hardness propagates.

The direction of reduction matters enormously. To show B is hard, reduce FROM a known-hard problem A TO B. Many beginners get this backwards. Remember: you are showing 'B is at least as hard as A' by showing 'I can use a solver for B to solve A.'

Transitivity. If A ≤_p B and B ≤_p C, then A ≤_p C (compose the reductions). This allows hardness to cascade.

What a good reduction proof looks like. (1) Describe f explicitly. (2) Prove f runs in polynomial time. (3) Prove the forward direction: if x ∈ A then f(x) ∈ B. (4) Prove the backward direction: if f(x) ∈ B then x ∈ A. Steps 3 and 4 are the mathematical heart.

The most important reduction in all of complexity theory is 3-SAT ≤_p many problems, because 3-SAT is the standard 'source' problem for NP-hardness proofs.

# Illustrating the REDUCTION STRUCTURE (not the reduction itself)
# If we have a poly-time oracle SOLVE_B, we can solve A:

def solve_A_via_B(instance_of_A):
    instance_of_B = reduce_A_to_B(instance_of_A)   # polynomial-time step
    answer_for_B  = SOLVE_B(instance_of_B)          # call oracle for B
    return answer_for_B
    # Correctness: instance_of_A is YES-instance <=> instance_of_B is YES-instance
    # (by the reduction's correctness proof)

# Concrete example: INDEPENDENT-SET <=_p CLIQUE
# G has an independent set of size k  <=>  complement(G) has a clique of size k

def reduce_IS_to_clique(G, k):
    """G is an adjacency set. Returns (G_complement, k)."""
    n = len(G)
    G_comp = {}
    for v in range(n):
        G_comp[v] = set()
        for u in range(n):
            if u != v and u not in G[v]:
                G_comp[v].add(u)
    return G_comp, k
# Proof sketch:
# (=>) S is indep set in G => no edges in G among S
#      => all edges present in G_comp among S => S is clique in G_comp
# (<=) S is clique in G_comp => all edges in G_comp among S
#      => no edges in G among S => S is indep set in G

With reductions established, we can define the two central hardness notions.

NP-hard. A problem H is NP-hard if every problem in NP reduces to H in polynomial time: for all L ∈ NP, L ≤_p H. NP-hard means 'at least as hard as everything in NP.' Crucially, H need not be in NP — NP-hard problems can be harder than NP (e.g., the halting problem is NP-hard).

NP-complete. A problem C is NP-complete if (1) C ∈ NP, and (2) C is NP-hard. NP-complete problems are the 'hardest problems in NP' — they sit exactly at the frontier. If any NP-complete problem is in P, then P = NP.

The canonical NP-complete problem. SAT (Boolean satisfiability): given a Boolean formula, does there exist a truth assignment making it true? Cook proved in 1971 (independently Levin in the Soviet Union) that SAT is NP-complete. This is the Cook-Levin theorem, and it required showing every NP computation can be encoded as a SAT instance — a highly non-trivial simulation argument.

The NP-completeness proof template. To show problem X is NP-complete: (1) Show X ∈ NP (give a polynomial-time verifier). (2) Show X is NP-hard by picking a known NP-complete problem Y and proving Y ≤_p X. Step 2 is the creative part; it shows 'X is at least as hard as Y, which is already NP-hard.'

The web of reductions. Once Cook proved SAT is NP-hard, Karp (1972) gave 21 NP-complete problems by a chain of reductions. Today thousands of problems are known NP-complete, all connected in a giant directed reduction graph.

# Pseudocode template for an NP-completeness proof

# Theorem: PROBLEM_X is NP-complete.
# Proof:
#
# Part 1: X in NP
#   Given instance I and certificate C:
#     - Describe what C looks like (e.g., a subset, an assignment, a path)
#     - Show |C| = O(|I|^k) for some k (certificate is polynomial-size)
#     - Show C can be verified in polynomial time
#
# Part 2: X is NP-hard  (reduce KNOWN_NP_COMPLETE <=_p X)
#   def reduce(instance_of_KNOWN):
#       ... polynomial-time construction ...
#       return instance_of_X
#
#   Correctness:
#   (=>) Assume instance_of_KNOWN is a YES instance.
#        Show reduce(instance_of_KNOWN) is a YES instance of X.
#
#   (<=) Assume reduce(instance_of_KNOWN) is a YES instance of X.
#        Show instance_of_KNOWN is a YES instance.
#
# Conclusion: X in NP and NP-hard => X is NP-complete.

The Cook-Levin theorem is one of the most profound results in mathematics. Its claim: every NP computation can be encoded as a SAT instance in polynomial time, so SAT is NP-hard. Combined with SAT being obviously in NP, SAT is NP-complete.

The proof idea. Let L ∈ NP, so there is a polynomial-time nondeterministic Turing machine M that accepts L, running in time p(n). For a given input x, we need to construct a Boolean formula φ_x such that φ_x is satisfiable iff x ∈ L.

The key insight: a computation of M on x is a tableau — a p(n) × p(n) table where row i is the complete machine configuration at step i. The formula φ_x has variables describing every cell of this tableau, and clauses encoding:

1. Initialization: row 0 is the initial configuration with input x.
2. Transition: each row follows from the previous by M's transition function.
3. Acceptance: some row contains an accepting state.

Each constraint becomes a small constant number of clauses over a constant number of cells. The total formula has O(p(n)²) variables and clauses — polynomial size.

A satisfying assignment to φ_x encodes exactly an accepting computation path of M on x. So φ_x is satisfiable iff x ∈ L. The reduction f: x ↦ φ_x runs in polynomial time. Since this works for every L ∈ NP, SAT is NP-hard.

Why 3-SAT is also NP-complete. Any Boolean formula can be converted to 3-CNF (conjunctive normal form with exactly 3 literals per clause) in polynomial time using the Tseitin transformation, which introduces auxiliary variables. So SAT ≤_p 3-SAT, and since SAT is NP-hard, so is 3-SAT. And 3-SAT ∈ NP trivially. So 3-SAT is NP-complete.

Historical note. Cook's 1971 paper 'The Complexity of Theorem Proving Procedures' was initially met with skepticism — reviewers were not sure it was significant. Within a year, Karp's reduction chain made clear this was the central concept in complexity theory.

# Tseitin transformation: convert any CNF clause of size > 3 into 3-CNF
# Long clause (a1 OR a2 OR ... OR ak) for k > 3 becomes:
# Introduce fresh variable y:
# (a1 OR a2 OR y) AND (NOT y OR a3 OR a4 OR ... OR ak)
# Recurse until all clauses have <= 3 literals.
# This is polynomial — at most k-3 new variables and clauses per original clause.

def to_3cnf(clause, next_var):
    """Reduce a clause (list of literals) to a list of 3-literal clauses.
    next_var: mutable int, counter for fresh variables.
    Returns (list_of_3clauses, new_next_var)."""
    if len(clause) <= 3:
        # Pad to length 3 by repeating a literal (a OR a OR b is logically same)
        while len(clause) < 3:
            clause = clause + [clause[0]]
        return [tuple(clause)], next_var
    # Split: (a[0] OR a[1] OR y) AND reduce(NOT y OR a[2:])
    y = next_var
    next_var += 1
    first_clause = (clause[0], clause[1], y)
    rest_clauses, next_var = to_3cnf([-y] + clause[2:], next_var)
    return [first_clause] + rest_clauses, next_var

# Example:
clauses_out, _ = to_3cnf([1, 2, 3, 4, 5], next_var=100)
for c in clauses_out:
    print(c)
# (1, 2, 100) AND (-100, 3, 4) AND ... each has exactly 3 literals

Beyond SAT, hundreds of natural combinatorial problems are NP-complete. Understanding a few canonical ones — and the reductions between them — builds the intuition to recognize NP-complete structure.

3-SAT ≤_p Independent Set. Given a 3-CNF formula with m clauses and n variables, build a graph G: for each clause, create a triangle (3 nodes for 3 literals); add an edge between any two nodes in different triangles that represent contradictory literals (x and ¬x). The formula has a satisfying assignment iff G has an independent set of size m. Key: choosing one true literal per clause, with no contradictions, corresponds exactly to an independent set picking one node from each triangle.

Independent Set ≤_p Clique. Take complement of graph. An independent set of size k in G is a clique of size k in Ḡ.

Independent Set ≤_p Vertex Cover. S is an independent set iff V \ S is a vertex cover. So G has an IS of size k iff G has a VC of size |V| - k.

3-SAT ≤_p 3-Dimensional Matching (3DM). A more intricate gadget construction, but follows the same pattern.

3-SAT ≤_p Subset Sum. Given n variables and m clauses, encode variables and clauses as carefully chosen integers. Satisfying assignments correspond to subsets summing to a target. The integers use base-(m+1) to avoid carry.

The Hamiltonian Path problem. 3-SAT ≤_p HAMPATH via a gadget that encodes variable assignments as the direction a traversal takes through a 'choice gadget' and clauses as detours.

Graph coloring. 3-coloring of a graph is NP-complete. 3-SAT ≤_p 3-COLOR using variable gadgets (two connected nodes force different colors = TRUE/FALSE) and clause gadgets.

Common structure. Most reductions share a pattern: variable gadgets (components encoding TRUE/FALSE for each variable), clause gadgets (components that are satisfiable only if the clause is satisfied), and consistency gadgets (ensuring the same variable has the same value everywhere).

# 3-SAT -> Independent Set reduction (the construction)
# Karp 1972

def sat_to_independent_set(clauses, n_vars):
    """
    clauses: list of 3-tuples of literals (integers, x>0 positive, x<0 negative)
    Returns (edges, target_k) for the Independent Set instance.
    nodes are labeled (clause_index, literal_index) i.e. (i, j) for j in {0,1,2}
    """
    edges = set()
    # Within each clause: connect all 3 literals to each other (form a triangle)
    for i, clause in enumerate(clauses):
        for j1 in range(3):
            for j2 in range(j1+1, 3):
                edges.add(((i, j1), (i, j2)))

    # Across clauses: connect complementary literals
    for i1, clause1 in enumerate(clauses):
        for j1, lit1 in enumerate(clause1):
            for i2, clause2 in enumerate(clauses):
                if i2 <= i1: continue
                for j2, lit2 in enumerate(clause2):
                    if lit1 == -lit2:   # x and NOT x are contradictory
                        edges.add(((i1, j1), (i2, j2)))

    k = len(clauses)   # looking for IS of this size
    return edges, k

# Correctness proof sketch:
# (=>) satisfying assignment A exists -> pick node (i, j) where literal j in clause i
#      is True under A. No two picked nodes conflict (same clause: can't pick 2;
#      different clauses: picked literals are both True so not complementary)
#      => independent set of size m.
# (<=) IS S of size m -> |S inter triangle_i| = 1 for each i (pigeonhole + triangles).
#      For each variable x: if (i,j) in S and literal is x, set x=True; if NOT x, False.
#      No contradiction (cross-clause edges block complementary literals).
#      => satisfying assignment.

In research and in competitive CS courses, you will frequently need to prove that a new problem is NP-complete. This is a skill that takes practice. Here is the systematic approach used by theoreticians.

Step 0: Smell test. Does the problem involve optimizing over an exponentially large set of configurations? Is it 'find a subset/ordering/assignment that satisfies some global condition'? Does small change to input seem to require re-doing all work? These are NP-complete hallmarks.

Step 1: Prove membership in NP. Describe the certificate explicitly (what does a witness for a YES instance look like?). Argue it has polynomial size. Argue the verifier runs in polynomial time. This step is usually easy but must not be skipped.

Step 2: Choose the right source problem. Don't always reduce from 3-SAT. Use the simplest source whose structure most naturally maps to your problem:

• Graph problems → reduce from IS, Clique, VC, or 3-COLOR
• Arithmetic/set problems → reduce from Subset Sum or Partition
• Sequencing/ordering → reduce from Hamiltonian Path/Cycle or TSP
• Tiling/packing → 3-DM or Exact Cover
• When in doubt → 3-SAT (most versatile)

Step 3: Build gadgets. Think of gadgets as LEGO bricks. Variable gadgets represent a binary choice. Clause gadgets are satisfied iff some condition holds. Consistency gadgets link copies of the same variable. You assemble these into one instance of your target problem.

Step 4: Prove correctness (the iff). The forward direction (YES source => YES target) usually follows directly from how you built the gadgets. The backward direction (YES target => YES source) requires showing that any valid solution to the target must 'decode' to a valid solution to the source — that there's no way to satisfy the target except via a legitimate encoding.

Step 5: Polynomial size. Confirm the construction produces an instance of size polynomial in the source instance size.

A worked example: INDEPENDENT SET IN INTERVAL GRAPHS is in P. This illustrates that restricting the graph class can push a problem into P, so the intractability of general IS doesn't apply. Recognizing problem structure can change everything.

# Reduction template: 3-SAT ->_p YOUR_PROBLEM
# Fill in the blanks for your specific reduction.

def reduce_3sat_to_your_problem(clauses, n_vars):
    """
    Input:  3-CNF formula with 'n_vars' variables and 'len(clauses)' clauses.
    Output: instance of YOUR_PROBLEM.

    Construction:
      For each variable x_i (i = 1..n_vars):
        Create VARIABLE GADGET that encodes x_i = True or x_i = False.
        [Your gadget construction here]

      For each clause C_j = (a OR b OR c):
        Create CLAUSE GADGET that is satisfiable iff at least one of a, b, c is True.
        [Your gadget construction here]

      Add CONSISTENCY GADGETS to ensure the same variable assignment is used
      in all clause gadgets that reference it.
        [Your gadget construction here]

    Claim: formula is satisfiable  <=>  YOUR_PROBLEM instance is a YES-instance.

    Proof (=>): Assume satisfying assignment A.
      - For each variable: configure its gadget according to A.
      - For each clause: since the clause is True under A, at least one literal
        is True; the clause gadget is therefore satisfied.
      - => YES instance of YOUR_PROBLEM.

    Proof (<=): Assume YES instance of YOUR_PROBLEM (valid solution S).
      - Decode variable assignments from S using the variable gadgets.
      - Argue that the consistency gadgets force the same value everywhere.
      - Argue that each clause gadget being satisfied forces the decoded
        assignment to satisfy the clause.
      - => satisfying assignment for the formula.
    """
    pass

Proving a problem NP-complete does not mean you stop working on it — it means you shift strategy. Three main approaches: approximation, fixed-parameter tractability, and exact exponential algorithms.

Approximation algorithms find solutions provably close to optimal in polynomial time. For a minimization problem, a ρ-approximation algorithm runs in polynomial time and always returns a solution of cost ≤ ρ · OPT. For maximization, cost ≥ (1/ρ) · OPT.

Vertex Cover: a 2-approximation. Repeatedly pick any uncovered edge (u,v), add both endpoints to the cover, remove all edges incident to u or v. This greedy runs in O(m) and always produces a cover of size ≤ 2·OPT. Proof: the matching found (all picked edges) is a maximal matching M. Any vertex cover must include at least one endpoint of each edge in M, so OPT ≥ |M|. We added 2|M| vertices, so our cover ≤ 2·OPT. Simple and elegant.

TSP with triangle inequality: a 1.5-approximation (Christofides-Serdyukov). The famous 1.5-approximation for metric TSP (Christofides 1976) uses a minimum spanning tree + minimum-weight perfect matching on odd-degree vertices to build an Eulerian multigraph, then shortcut. Improvement to 1.5-ε announced in 2020 (Karlin, Klein, Gharan).

Hardness of approximation. For some problems, even getting within a constant factor of optimal is NP-hard. MAX-3-SAT can be approximated to 7/8 by a randomized assignment (just set each variable uniformly at random!), and Håstad showed this cannot be improved to 7/8 + ε unless P = NP. This uses the PCP theorem — a deep result that says NP = PCP[O(log n), O(1)], meaning NP proofs can be checked by reading only a constant number of bits.

Inapproximability example: Set Cover. Set Cover admits an O(log n) approximation (greedy: always pick the set covering the most uncovered elements). Feige (1998) showed this is tight: no (1-ε) ln n approximation exists unless P = NP.

# 2-approximation for Vertex Cover

def approx_vertex_cover(adj):
    """
    adj: dict mapping each vertex to its neighbor set.
    Returns a vertex cover C with |C| <= 2 * OPT.
    """
    covered = set()
    C = set()
    for u in adj:
        for v in adj[u]:
            if u not in covered and v not in covered:
                # edge (u,v) not yet covered; take both endpoints
                C.add(u)
                C.add(v)
                covered.add(u)
                covered.add(v)
    return C

# Verification (optional, O(m)):
def is_vertex_cover(adj, C):
    for u in adj:
        for v in adj[u]:
            if u not in C and v not in C:
                return False  # edge not covered
    return True

# Approximation ratio proof:
# Let M = set of edges we picked (one per iteration)
# M is a *maximal matching* (no two edges share an endpoint)
# Any vertex cover must hit every edge in M, so OPT >= |M|
# We added |2*M| vertices => |C| = 2|M| <= 2*OPT  QED

Approximation gives up optimality. Fixed-parameter tractability (FPT) is a different cope: find an exact algorithm whose exponential blowup is confined to a small parameter of the input rather than the full input size.

A problem with parameter k is in FPT if it can be solved in time f(k) · poly(n) for some computable function f. If k is small (e.g., the treewidth of a graph, or the solution size), this can be very fast even though f(k) might be 2^k or k!.

Vertex Cover parameterized by k (solution size): Does G have a vertex cover of size ≤ k? A naive approach tries all C(n, k) subsets — exponential in n. An FPT approach: pick any edge (u, v); any cover must contain u or v; branch into two subproblems with k reduced by 1 each. This gives a recursion tree of depth k with branching factor 2 → O(2^k) leaves → total time O(2^k · n). For k ≤ 30 this is perfectly practical even with n = 10^6.

Kernelization. A complementary technique: in polynomial time, reduce any instance to an 'equivalent kernel' of size bounded by f(k). For Vertex Cover: any vertex of degree > k must be in any size-k cover; include it and reduce k. After this preprocessing, if any vertex has degree > k, include it; otherwise, the remaining graph has at most k² edges (each of ≤ k vertices contributing ≤ k edges). So we reduce to an instance of size O(k²) before running the exponential-time algorithm.

The W-hierarchy. Not all parameterized problems are FPT. INDEPENDENT SET parameterized by k is W[1]-complete under parameterized reductions, meaning it is believed to require n^Ω(k) time — the exponential blowup cannot be separated from n. This is analogous to NP-completeness but in the parameterized world.

Practical impact. FPT algorithms are widely deployed in bioinformatics (phylogenetics, haplotyping) and network analysis where parameters like treewidth or solution size are empirically small.

# FPT algorithm for Vertex Cover parameterized by k
# O(2^k * n) time

def vertex_cover_fpt(adj, k):
    """
    Returns a vertex cover of size <= k, or None if none exists.
    adj: dict {vertex: set_of_neighbors}.
    """
    # Find any uncovered edge
    edge = None
    for u in adj:
        for v in adj[u]:
            edge = (u, v)
            break
        if edge:
            break

    if edge is None:
        return set()   # No edges left: empty cover works

    if k == 0:
        return None    # Edges remain but no budget left

    u, v = edge
    # Branch: include u OR include v
    for chosen in (u, v):
        # Remove 'chosen' and all its edges from the graph
        new_adj = {}
        for x in adj:
            if x == chosen:
                continue
            new_adj[x] = adj[x] - {chosen}
        result = vertex_cover_fpt(new_adj, k - 1)
        if result is not None:
            return result | {chosen}

    return None  # Neither branch found a cover of size k

# With kernelization preprocessing this becomes even faster in practice:
# any vertex of degree > k must be in the cover; include it greedily first.

The question 'Does P = NP?' is one of the seven Millennium Prize Problems, carrying a $1,000,000 prize. Despite decades of effort, neither a proof that P = NP nor a proof that P ≠ NP has been found.

The majority belief. Most complexity theorists believe P ≠ NP — that there is a fundamental difference between finding and verifying. The intuitive argument: if P = NP, we could efficiently solve protein folding, circuit minimization, natural language understanding, and break all public-key cryptography. The world would look radically different.

Barriers to proof. Three formal barriers explain why P vs NP has resisted attack:

• Relativization (Baker-Gill-Solovay 1975): almost all known proof techniques relativize, meaning they work in any model with an oracle. But relative to some oracles P = NP, and relative to others P ≠ NP — so relativizing techniques cannot settle P vs NP.
• Natural proofs (Razborov-Rudich 1994): any 'natural' proof technique (formalized precisely) that proves superpolynomial lower bounds would also yield an algorithm to break pseudorandom generators — contradicting cryptographic assumptions. So natural proof techniques won't work.
• Algebrization (Aaronson-Wigderson 2009): an extension of relativization that blocks algebraic proof techniques.

Consequences if P = NP. Cryptography as we know it fails; NP-complete optimization problems (TSP, protein design, drug discovery) become tractable; mathematical theorem proving becomes automatable (a satisfying proof of any NP-provable theorem could be found in polynomial time). The intellectual and economic consequences would dwarf any other mathematical discovery.

Consequences if P ≠ NP (the expected case). Current cryptographic foundations are justified. NP-complete problems are provably intractable in the worst case. Approximation and FPT algorithms are the right tools.

The structure inside NP. Even if P ≠ NP, there may be problems in NP that are neither in P nor NP-complete (Ladner's theorem: if P ≠ NP, then NP-intermediate problems exist). Candidates: graph isomorphism (GI), integer factorization, discrete logarithm. GI is not known to be NP-complete and has a quasi-polynomial algorithm (Babai 2016).

# Illustrating Ladner's theorem conceptually:
# If P != NP, the complexity landscape has three regions:
#
#  +------------------------------------------+
#  |                  NP                      |
#  |  +----------+   +-----------+  +------+  |
#  |  |    P     |   |    NP-    |  |  NP- |  |
#  |  | (easy)   |   |Intermediate|  |complete|  |
#  |  +----------+   +-----------+  +------+  |
#  +------------------------------------------+
#
# P examples:          2-SAT, matching, shortest path, primality
# NP-intermediate(?):  Graph Isomorphism, Factoring
# NP-complete:         3-SAT, IS, VC, TSP, 3-COLOR, ...
#
# Note: no NP-intermediate problem is *proved* to be intermediate;
# we only know they exist non-constructively (Ladner 1975).
#
# The 'hardness' ordering is a partial order under <=_p:
# P <= NP-intermediate <= NP-complete <= NP-hard
# (with proper subset relationships if P != NP)

NP-completeness lives in the time complexity world, but problems also have space complexity, and the two hierarchies interleave in surprising ways.

PSPACE. The class of problems solvable in polynomial space (but potentially exponential time). PSPACE ⊇ NP and PSPACE ⊇ co-NP, but whether PSPACE = NP is open. PSPACE-complete problems include TQBF (true quantified Boolean formulas) and planning with complete information.

EXP. Problems solvable in exponential time. NP ⊆ EXP (exponential time can verify all possible certificates). EXP-complete problems include certain game problems like n×n chess (optimal play).

Why this matters for NP. NP ⊆ PSPACE: verify a certificate by iterating over all possible certificates in polynomial space (though exponential time). So the full chain is:

P ⊆ NP ⊆ PSPACE ⊆ EXP

We know P ≠ EXP (time hierarchy theorem), but we don't know which of the ⊆ above are strict, except that at least one of P⊊NP or NP⊊PSPACE must hold.

#P and counting problems. Beyond decision problems, #P counts the number of accepting certificates. #P-complete problems include: counting the satisfying assignments of a formula (#SAT), computing the permanent of a 0/1 matrix (Valiant 1979). Surprisingly, #P can be hard even for problems in P: counting perfect matchings in a bipartite graph (finding one is easy, counting is #P-complete).

Randomized complexity. BPP (bounded-error probabilistic polynomial time) is the class of problems solvable by a polynomial-time randomized algorithm with error ≤ 1/3. It is widely believed BPP = P, and Adleman showed BPP ⊆ P/poly. Primality testing was in BPP before the AKS algorithm moved it into P.

# The complexity hierarchy — key containments
# (pseudocode as a set containment diagram)

# Inclusions known:
# L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ NEXP
# NP ⊆ PH ⊆ PSPACE
# BPP ⊆ Σ_2^P (in the polynomial hierarchy)
# Separations known:
# L ≠ PSPACE (space hierarchy), P ≠ EXP (time hierarchy)
# Not known whether: P = NP, NP = co-NP, NP = PSPACE

# Problem placement:
classes = {
    'P':       ['2-SAT', 'matching', 'primality', 'LP', 'SCC'],
    'NP\\P?':  ['Graph Isomorphism', 'Factoring'],      # if P != NP
    'NP-c':    ['3-SAT', 'IS', 'VC', 'TSP-decision', '3-COLOR'],
    'PSPACE-c':['TQBF', 'Generalized Geography', 'QBF-planning'],
    'EXP-c':   ['n×n Chess', 'n×n Go optimal play'],
    '#P-c':    ['#SAT', 'permanent', '#matching'],
}
for cls, problems in classes.items():
    print(f'{cls}: {problems}')