NP-Completeness in Depth

Complexity theory works most cleanly with decision problems — problems with a yes/no answer. Any optimization problem can be turned into a decision problem by adding a threshold parameter (e.g., "Is there a tour of length ≤ k?" instead of "Find the shortest tour").

Formally, a decision problem is a language L ⊆ Σ* — a set of strings over some alphabet Σ. We say a Turing machine M decides L if M(x) = YES iff x ∈ L, and M always halts.

The class P is the set of all languages L for which there exists a deterministic Turing machine that decides L in time O(n^k) for some constant k, where n = |x|. Polynomial time is the threshold for "efficiently solvable" by the Church-Turing thesis analog for efficiency.

Examples in P:

• PRIMES: is n prime? (AKS algorithm, 2002, O(log^6 n))
• SORTING: is array A sorted? (trivially O(n))
• SHORTEST-PATH: is there a path from s to t of length ≤ k in graph G? (Dijkstra, O(E log V))
• 2-SAT: is a 2-CNF formula satisfiable? (linear time via strongly connected components)

The Church-Turing thesis says polynomial time is robust: it does not change if you use multi-tape TMs, RAMs, or any other reasonable model. This is why P is a meaningful class.

Analogy: P is the drawer of "easy" problems — not necessarily fast in practice, but tractable in principle, with running time that does not blow up catastrophically as input grows.

# Checking 2-SAT in Python (simplified)
# A 2-CNF formula is satisfiable iff no variable x
# has both x and ¬x in the same SCC of the implication graph.

def two_sat(n, clauses):
    """
    n: number of variables (1..n)
    clauses: list of (a, b) meaning (a OR b),
             where negative index means negation.
    Returns True if satisfiable.
    """
    # Build implication graph: (a OR b) = (NOT a => b) AND (NOT b => a)
    graph = [[] for _ in range(2 * n + 1)]
    rgraph = [[] for _ in range(2 * n + 1)]

    def var(x):
        return x if x > 0 else n - x  # encode negation

    for a, b in clauses:
        na, nb = -a, -b
        graph[var(na)].append(var(b))
        graph[var(nb)].append(var(a))
        rgraph[var(b)].append(var(na))
        rgraph[var(a)].append(var(nb))

    # Kosaraju's SCC (two-pass DFS) — O(V + E)
    # ... (standard implementation)
    # If var(x) and var(-x) are in same SCC => UNSAT
    pass  # Full Kosaraju omitted for brevity; the key is it runs in O(n+m)

NP (Nondeterministic Polynomial time) is the class of decision problems for which a yes answer can be verified in polynomial time given a short certificate (also called a witness).

Formal definition (verifier-based, the modern preferred form): L ∈ NP iff there exists a polynomial-time deterministic TM V and a polynomial p such that:

• For all x ∈ L, there exists a certificate c with |c| ≤ p(|x|) such that V(x, c) = YES.
• For all x ∉ L and all c, V(x, c) = NO.

V is called the verifier. The certificate is the "hint" that makes checking easy.

Examples in NP:

• SAT: given a Boolean formula, certificate = a satisfying assignment. Checking takes O(n).
• HAMILTONIAN-PATH: certificate = the path itself. Checking takes O(n).
• CLIQUE: certificate = the k vertices. Checking takes O(k^2).
• SUBSET-SUM: certificate = the subset. Checking takes O(n).

The nondeterministic TM definition (equivalent): NP is the class of languages decided in polynomial time by a nondeterministic TM — one that can fork into multiple computation paths simultaneously. It accepts if any path accepts. This is where the "N" comes from.

Crucial insight: P ⊆ NP, because any polynomial verifier can ignore the certificate and just solve the problem itself. The open question is whether NP ⊆ P — that is, whether P = NP.

co-NP is the class of problems whose no instances have polynomial certificates. TAUTOLOGY (is every assignment satisfying?) ∈ co-NP. Note: NP ≠ co-NP is also unproven, but believed true.

Intuition: NP is the class of problems where you can get lucky — a magical oracle guesses the certificate instantly, then you verify it quickly. P is the class where you don't need luck.

# The NP verifier pattern — illustrated for SUBSET-SUM
# L = {(S, t) : some subset of S sums to t}
# Certificate: the subset indices.

def verify_subset_sum(S, t, certificate):
    """
    S: list of integers
    t: target integer
    certificate: list of indices claimed to form a subset summing to t
    Returns True iff certificate is a valid witness for (S, t) in SUBSET-SUM.
    Runs in O(|certificate|) = O(n) — polynomial in input size.
    """
    if not all(0 <= i < len(S) for i in certificate):
        return False
    if len(set(certificate)) != len(certificate):  # no duplicates
        return False
    return sum(S[i] for i in certificate) == t

# The SEARCH problem (finding the certificate) can take O(2^n) brute force.
# The VERIFICATION problem takes O(n). This asymmetry defines NP.

A polynomial-time (many-one) reduction from language A to language B, written A ≤_p B, is a function f computable in polynomial time such that:

x ∈ A ⟺ f(x) ∈ B

Intuitively: if you have a black-box solver for B, you can solve A in polynomial time by transforming every A-instance into a B-instance.

Key properties:

1. Transitivity: if A ≤_p B and B ≤_p C, then A ≤_p C.
2. Upward closure: if A ≤_p B and B ∈ P, then A ∈ P.
3. Contrapositive: if A ≤_p B and A ∉ P, then B ∉ P.

Reductions are the language of complexity theory. They let us compare the difficulty of problems without solving them.

Example sketch — INDEPENDENT-SET ≤_p CLIQUE: Given graph G = (V, E) and integer k, we want to know if G has an independent set of size k (a set of k vertices with no edge between them). We reduce to CLIQUE on the complement graph Ḡ = (V, Ē) where Ē = {(u,v) : (u,v) ∉ E}. Then:

G has an independent set of size k ⟺ Ḡ has a clique of size k.

Proof: vertices mutually non-adjacent in G become mutually adjacent in Ḡ. The transformation f(G, k) = (Ḡ, k) runs in O(V^2) time. Done.

Karp reduction vs. Cook reduction: Karp (many-one, above) maps instances. Cook (Turing) allows calling the oracle multiple times. NP-hardness via Cook reductions is slightly weaker; we almost always mean Karp reductions in NP-completeness proofs.

Analogy: reductions are like currency exchange. If you can convert dollars to euros efficiently, and euros buy things at a certain rate, then dollars buy things at (roughly) the same rate. Hardness is preserved going in the direction of the reduction.

# Reduction: INDEPENDENT-SET ≤_p CLIQUE
# Transform instance (G, k) of INDEP-SET into instance (G_bar, k) of CLIQUE

def complement_graph(n, edges):
    """
    n: number of vertices (0..n-1)
    edges: set of (u, v) pairs with u < v
    Returns complement graph edges.
    Runs in O(n^2).
    """
    all_edges = {(u, v) for u in range(n) for v in range(u+1, n)}
    return all_edges - edges

def reduce_indepset_to_clique(n, edges, k):
    """
    (G, k) is a YES instance of INDEP-SET
    iff (complement(G), k) is a YES instance of CLIQUE.
    """
    return n, complement_graph(n, edges), k

# To solve INDEP-SET using a CLIQUE oracle:
# result = clique_oracle(*reduce_indepset_to_clique(n, edges, k))
# This is a correct poly-time Karp reduction.

NP-hard: A problem H is NP-hard if every problem in NP reduces to H in polynomial time:

∀ L ∈ NP, L ≤_p H

NP-hard problems are at least as hard as every problem in NP. Note: NP-hard does not require H to be in NP — H could be undecidable (e.g., the Halting Problem is NP-hard).

NP-complete: A problem C is NP-complete if:

1. C ∈ NP (there is a polynomial-time verifier)
2. C is NP-hard (every NP problem reduces to C)

NP-complete problems are exactly the hardest problems within NP. They sit at the top of the NP mountain.

Why NP-completeness matters:

• If any NP-complete problem has a polynomial-time algorithm, then P = NP and every problem in NP is polynomial.
• If any NP problem is not in P, then no NP-complete problem is in P either (since all NP problems reduce to it).
• NP-complete problems are computationally equivalent under polynomial reduction — they form a single equivalence class of hardness.

The picture so far (assuming P ≠ NP):

• P: problems solvable in poly time (easy)
• NP \ P: problems in NP but not in P (hard to solve, easy to verify)
• NP-complete: the hardest problems in NP
• NP-hard \ NP: harder than anything in NP (e.g., PSPACE-complete, undecidable)

Practical consequence: when you encounter an optimization problem and suspect it is NP-complete:

1. Show it is in NP (find a polynomial verifier).
2. Reduce a known NP-complete problem to it. Then stop looking for a polynomial exact algorithm and explore approximations or special-case structures.

# Pseudocode: Template for an NP-completeness proof

# To prove problem X is NP-complete:

# STEP 1: Show X is in NP
# -------------------------
def verifier_X(instance, certificate):
    # Check certificate has polynomial length
    # Check certificate encodes a valid solution
    # Return True/False in polynomial time
    pass

# STEP 2: Show X is NP-hard
# -------------------------
# Choose a known NP-complete problem Y (e.g., 3-SAT, CLIQUE, VERTEX-COVER)
# Construct a polynomial-time function f such that:
#   instance y of Y is YES  <=>  f(y) is a YES instance of X

def reduction_Y_to_X(y):
    # Transform instance y of Y into instance x of X
    # This must run in polynomial time
    # Prove correctness: y in Y <=> x in X
    return x

# Then conclude: X is NP-complete.

The Cook-Levin theorem (Cook 1971, Levin independently 1973) is the foundational result of complexity theory:

Theorem: SAT is NP-complete.

SAT (Boolean Satisfiability): Given a Boolean formula φ over variables x_1, …, x_n (using AND, OR, NOT), does there exist a truth assignment that makes φ true?

SAT is clearly in NP: the certificate is the satisfying assignment, and checking it takes O(n) time.

The hard part: proving SAT is NP-hard — that every problem in NP reduces to SAT in polynomial time.

Proof sketch: Let L be any language in NP, with verifier V running in time p(n). We must construct a polynomial-time f such that x ∈ L ⟺ f(x) is satisfiable.

The key idea: simulate the verifier V as a Boolean circuit, then encode the circuit as a SAT formula.

1. V runs in time p(n), so its entire computation on input (x, c) occupies a tableau of size p(n) × p(n) — one row per time step, one column per tape cell. The tableau is completely determined by the initial configuration (x, c) and the TM transition function.

2. Introduce a Boolean variable for each cell in the tableau. The formula φ_x has:

   • Boundary conditions: clauses encoding V's initial tape contents (the known input x).
   • Transition clauses: for each time step t and cell j, clauses encoding that cell (t+1, j) is determined by the local neighborhood at time t (TM rules only look at a constant neighborhood).
   • Acceptance clauses: clauses saying that at time p(n), the TM is in the accept state.
   • Certificate variables: the cells encoding c are free variables.

3. φ_x is satisfiable ⟺ some setting of the certificate variables makes V accept ⟺ x ∈ L.

4. φ_x has O(p(n)^2) variables and O(p(n)^2) clauses — polynomial in n. Construction takes polynomial time.

This proof is deep: it says that the mechanics of computation itself can be encoded in a Boolean formula. SAT is hard because it can simulate any polynomial-time computation.

Why this was shocking: Before Cook-Levin, there was no evidence that natural combinatorial problems should be related to each other in difficulty. Cook showed they all have the same underlying structure: they all secretly encode computation tableaux.

# Conceptual illustration: encoding a single TM transition step as clauses
# In a real Cook-Levin reduction, you would do this for all O(p(n)^2) cells.

# Suppose TM state q reads symbol s and writes s', moves right, enters q'.
# Variable notation: Q[t][q] = True if TM is in state q at time t
#                   H[t][j] = True if head is at cell j at time t
#                   T[t][j][s] = True if cell j contains symbol s at time t

# Transition clause (simplified, one step):
# IF Q[t][q] AND H[t][j] AND T[t][j][s] THEN Q[t+1][q'] AND H[t+1][j+1] AND T[t+1][j][s']

# Each such implication A => B becomes the clause (NOT A) OR B.
# Combined, these form a CNF formula of polynomial size.

# The FULL formula is:
# phi_x = (boundary conditions for input x)
#       AND (all transition clauses for time 0..p(n)-1)
#       AND (acceptance clause: Q[p(n)][q_accept])
#       AND (well-formedness clauses: exactly one state, head pos, symbol per cell)

# x is in L iff phi_x is satisfiable (free vars = certificate cells)
print("Cook-Levin: every NP problem reduces to SAT via computation tableau encoding")

3-SAT is the restriction of SAT to formulas in Conjunctive Normal Form (CNF) where every clause has exactly 3 literals.

A CNF formula is an AND of clauses, each clause is an OR of literals, and a literal is a variable or its negation. Example:

(x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x4) ∧ (x2 ∨ ¬x3 ∨ ¬x4)

Theorem: 3-SAT is NP-complete.

Proof: 3-SAT ∈ NP trivially. For NP-hardness, we reduce SAT to 3-SAT.

Given a SAT formula φ in CNF (arbitrary clause lengths), convert each clause to a set of 3-literal clauses by introducing helper variables:

• Clause with 1 literal (l): Replace with (l ∨ p ∨ q) ∧ (l ∨ p ∨ ¬q) ∧ (l ∨ ¬p ∨ q) ∧ (l ∨ ¬p ∨ ¬q). This is satisfiable iff l = TRUE.
• Clause with 2 literals (l1 ∨ l2): Replace with (l1 ∨ l2 ∨ p) ∧ (l1 ∨ l2 ∨ ¬p).
• Clause with k > 3 literals (l1 ∨ … ∨ lk): Introduce helper variables y1, …, y_{k-3} and replace with: (l1 ∨ l2 ∨ y1) ∧ (¬y1 ∨ l3 ∨ y2) ∧ (¬y2 ∨ l4 ∨ y3) ∧ … ∧ (¬y_{k-3} ∨ l_{k-1} ∨ lk) The chain is satisfiable iff at least one li is TRUE.

This produces a 3-CNF formula of polynomial size. SAT ≤_p 3-SAT, and since SAT is NP-hard, so is 3-SAT.

Why 3-SAT is the key pivot: Almost every subsequent NP-hardness proof in Karp's original 21 problems reduces from 3-SAT, not from general SAT or the abstract TM simulation. 3-SAT has just the right structure — rich enough to encode complex constraints, simple enough that reductions can carefully target graph or combinatorial properties.

2-SAT is in P: Two-literal clauses do not provide enough structure to encode all NP computations. This boundary — between 2-SAT (polynomial) and 3-SAT (NP-complete) — is a razor-thin but fundamental divide.

# Converting an arbitrary CNF clause to 3-literal clauses

def clause_to_3sat(clause, next_var):
    """
    clause: list of literals (integers, negative = negated variable)
    next_var: next available fresh variable index
    Returns (list_of_3_clauses, next_var_after)
    """
    k = len(clause)
    if k == 1:
        l = clause[0]
        p, q = next_var, next_var + 1
        new_clauses = [
            [l,  p,  q],
            [l,  p, -q],
            [l, -p,  q],
            [l, -p, -q],
        ]
        return new_clauses, next_var + 2
    elif k == 2:
        l1, l2 = clause
        p = next_var
        return [[l1, l2, p], [l1, l2, -p]], next_var + 1
    elif k == 3:
        return [clause], next_var
    else:
        # Chain construction for k > 3
        result = []
        y = next_var
        result.append([clause[0], clause[1], y])
        for i in range(2, k - 2):
            result.append([-y, clause[i], y + 1])
            y += 1
        result.append([-y, clause[k-2], clause[k-1]])
        return result, y + 1

def to_3sat(cnf_clauses):
    """Convert arbitrary CNF to 3-CNF. Returns list of 3-literal clauses."""
    all_clauses = []
    next_var = max(abs(l) for c in cnf_clauses for l in c) + 1
    for clause in cnf_clauses:
        new_c, next_var = clause_to_3sat(clause, next_var)
        all_clauses.extend(new_c)
    return all_clauses

CLIQUE: Given a graph G = (V, E) and integer k, does G contain a clique of size k (k mutually adjacent vertices)?

Theorem: CLIQUE is NP-complete. Proof: CLIQUE ∈ NP (certificate: the k vertices). For NP-hardness, we show 3-SAT ≤_p CLIQUE.

The reduction: Given a 3-CNF formula φ with m clauses C_1, …, C_m each containing 3 literals, construct a graph G and set k = m:

1. Vertices: For each clause C_i = (l_{i,1} ∨ l_{i,2} ∨ l_{i,3}), create three vertices v_{i,1}, v_{i,2}, v_{i,3} — one per literal. Total: 3m vertices.

2. Edges: Add edge (v_{i,a}, v_{j,b}) whenever:

   • i ≠ j (vertices are in different clauses), AND
   • l_{i,a} and l_{j,b} are consistent (not a variable and its negation).

Correctness: φ is satisfiable ⟺ G has a clique of size m.

• (→) Suppose φ is satisfiable. Pick a satisfying assignment. In each clause C_i, pick one true literal l_{i,a_i}. The m vertices {v_{1,a_1}, …, v_{m,a_m}} form a clique: they are from distinct clauses (so the edge condition i ≠ j is met), and any two chosen literals are consistent under the satisfying assignment (a literal and its negation cannot both be true).

• (←) Suppose G has a clique of size m. Since there are only 3m vertices in m groups of 3, and the clique has m vertices, exactly one vertex comes from each clause. The literal corresponding to each vertex can be set to TRUE. Vertices in the clique are pairwise consistent, so no variable is set to both TRUE and FALSE. Each clause has a true literal, so φ is satisfied.

The reduction runs in O(m^2) — polynomial.

This reduction is a beautiful example of encoding a combinatorial constraint (satisfying an assignment) as a structural property of a graph (a clique). The clauses become groups, the literals become vertices, and consistency becomes edges.

def three_sat_to_clique(clauses):
    """
    clauses: list of 3-literal clauses, each clause is [l1, l2, l3]
             where literals are integers (negative = negated)
    Returns (vertices, edges, k) for the CLIQUE instance.
    """
    m = len(clauses)
    # Vertices: (clause_index, literal_position) -> label
    vertices = [(i, j) for i in range(m) for j in range(3)]
    
    edges = set()
    for i in range(m):
        for j in range(m):
            if i >= j:
                continue  # different clauses only, avoid duplicates
            for a in range(3):
                for b in range(3):
                    lit_ia = clauses[i][a]
                    lit_jb = clauses[j][b]
                    # Consistent: not a variable and its negation
                    if lit_ia != -lit_jb:
                        edges.add(((i, a), (j, b)))
    
    k = m  # We need a clique of size = number of clauses
    return vertices, edges, k

# Example: (x1 OR NOT x2 OR x3) AND (NOT x1 OR x2 OR x4)
clauses = [[1, -2, 3], [-1, 2, 4]]
verts, edges, k = three_sat_to_clique(clauses)
print(f"{len(verts)} vertices, {len(edges)} edges, need clique of size {k}")

VERTEX COVER: Given a graph G = (V, E) and integer k, does there exist a set S ⊆ V with |S| ≤ k such that every edge (u, v) ∈ E has at least one endpoint in S?

Equivalently: S is a vertex cover iff V \ S is an independent set. So VERTEX-COVER and INDEPENDENT-SET are polynomial-time equivalent (complement the set, adjust k).

VERTEX-COVER is NP-complete. The reduction 3-SAT ≤_p VERTEX-COVER uses a beautiful gadget construction:

The reduction: Given a 3-CNF formula φ with n variables and m clauses:

1. Variable gadgets: For each variable x_i, add two vertices x_i and ¬x_i connected by an edge. We must pick at least one of them in any vertex cover (to cover the edge). This encodes the choice of setting x_i true or false.

2. Clause gadgets: For each clause C_j = (l_{j,1} ∨ l_{j,2} ∨ l_{j,3}), add a triangle on three new vertices c_{j,1}, c_{j,2}, c_{j,3}. A vertex cover must include at least 2 of the 3 triangle vertices (to cover all 3 triangle edges). The vertex NOT in the cover encodes which literal "satisfies" the clause.

3. Connecting edges: For each literal l_{j,r} in clause j, add an edge between c_{j,r} and the corresponding variable-gadget vertex (the vertex for literal l_{j,r}).

4. Set k = n + 2m (n gadget vertices + 2 per clause triangle).

Correctness sketch: The variable gadgets force a consistent truth assignment (n vertices chosen). The clause gadgets require 2m vertices. The connecting edges force: for each clause, at least one of its triangle vertices must be the one NOT in the cover, meaning its variable gadget vertex IS in the cover, meaning that literal is set to TRUE by the assignment. So the formula is satisfied iff the graph has a vertex cover of size n + 2m.

This chain so far: SAT → 3-SAT → CLIQUE, VERTEX-COVER, INDEPENDENT-SET. All NP-complete, all interreducible.

def three_sat_to_vertex_cover(n_vars, clauses):
    """
    n_vars: number of Boolean variables (1..n_vars)
    clauses: list of 3-literal clauses
    Returns (graph_edges, num_vertices, k) for VERTEX-COVER.
    
    Node encoding:
      - Variable x_i: nodes 2*(i-1) and 2*(i-1)+1  (for true/false literal)
      - Clause j triangle: nodes 2*n_vars + 3*j, 2*n_vars+3*j+1, 2*n_vars+3*j+2
    """
    m = len(clauses)
    edges = []
    
    # Variable gadget edges (one per variable)
    for i in range(n_vars):
        true_node = 2 * i
        false_node = 2 * i + 1
        edges.append((true_node, false_node))
    
    # Clause gadgets and connecting edges
    for j, clause in enumerate(clauses):
        base = 2 * n_vars + 3 * j
        c0, c1, c2 = base, base + 1, base + 2
        # Triangle
        edges += [(c0, c1), (c1, c2), (c0, c2)]
        # Connecting edges to variable gadgets
        for r, lit in enumerate(clause):
            # Map literal to variable-gadget node
            if lit > 0:
                var_node = 2 * (lit - 1)        # true literal
            else:
                var_node = 2 * (-lit - 1) + 1   # false literal
            edges.append((base + r, var_node))
    
    num_vertices = 2 * n_vars + 3 * m
    k = n_vars + 2 * m
    return edges, num_vertices, k

HAMILTONIAN-PATH: Given a directed graph G and vertices s, t, is there a simple path from s to t visiting every vertex exactly once?

HAMILTONIAN-CYCLE: Same, but a cycle (start and end at same vertex).

Both are NP-complete. The reduction typically goes VERTEX-COVER ≤_p HAMILTONIAN-PATH, or more directly via a reduction from 3-SAT using path gadgets and choice gadgets.

Reduction sketch (3-SAT ≤_p DIRECTED-HAMILTONIAN-PATH):

1. Variable gadgets: For each variable x_i, build a "zigzag" row of vertices. The Hamiltonian path can traverse the row left-to-right (encoding x_i = TRUE) or right-to-left (encoding x_i = FALSE). The path is forced to make a binary choice at each row.

2. Clause gadgets: For each clause C_j, add a single vertex c_j. The clause vertex is "visited" by the path using a detour from one of the variable rows corresponding to a literal in C_j. The detour is only available if the variable is set in the right direction for the literal to be true.

3. The path from s to t visits all variable rows (making truth assignments) and uses detours to visit all clause vertices (each clause must be satisfied by some literal).

TRAVELING SALESMAN PROBLEM (TSP) is NP-hard: Reduce HAMILTONIAN-PATH to TSP by assigning weight 1 to original edges and weight 2 to all others; then asking if there is a tour of total weight ≤ n. TSP is not only NP-hard but also hard to approximate within any constant factor unless P = NP (the Christofides algorithm gives a 3/2-approximation for metric TSP).

The full reduction web (Karp 1972): Karp showed 21 problems are NP-complete by building a DAG of reductions, all starting from 3-SAT or its close relatives:

3-SAT → CLIQUE → INDEPENDENT SET → VERTEX COVER 3-SAT → DIRECTED HAMILTONIAN CYCLE → UNDIRECTED HAMILTONIAN CYCLE → TSP 3-SAT → 3-DIMENSIONAL MATCHING → SET COVER, EXACT COVER 3-SAT → SUBSET SUM → PARTITION → KNAPSACK 3-SAT → BIN PACKING, JOB SCHEDULING, ...

Every reduction is elegant and instructive in its own right. The web now contains thousands of NP-complete problems spanning combinatorics, graph theory, number theory, logic, and AI.

# Pseudocode: structure of a Hamiltonian Path gadget-based reduction from 3-SAT

# Given: 3-CNF formula with n variables x1..xn and m clauses C1..Cm

# Build directed graph G:

# 1. Source s, sink t
# 2. For each variable xi:
#    Create row of 2m+3 nodes: [s_i, v_{i,1}, v_{i,2}, ..., v_{i,2m+2}, t_i]
#    Forward edges  (left-to-right): encode xi = TRUE
#    Backward edges (right-to-left): encode xi = FALSE
#    Chain rows: t_i -> s_{i+1}; s -> s_1; t_n -> t
# 3. For each clause Cj (involving literals la, lb, lc):
#    Create node cj
#    For each literal l in Cj:
#      Let xi be its variable, direction d (fwd if positive, bwd if negated)
#      Add edges: v_{i, 2j} -> cj -> v_{i, 2j+1}  (in direction d)
#      (detour: path can visit cj while traversing row i in direction d)

# Correctness:
# Ham-path from s to t  <=>  assignment satisfying phi
# - Each row traversal direction sets a variable
# - Each clause node cj is visited via a detour from a row of a satisfying literal
# - All n + m + 2 nodes visited exactly once

print("Hamiltonian path gadgets encode variable assignment + clause satisfaction")
print("This gives: 3-SAT ≤_p HAM-PATH in polynomial time")

The P vs. NP question, posed by Cook (1971) and Gödel in a letter to von Neumann (1956), is:

Does P = NP?

Almost everyone believes P ≠ NP, but no proof exists. It is one of the Clay Millennium Prize Problems ($1 million).

Why P ≠ NP is believed:

1. Thousands of natural NP-complete problems have been studied for 50+ years; none has been solved in polynomial time.
2. Random oracle results suggest separation (Baker, Gill, Solovay 1975).
3. Proof complexity lower bounds give evidence that SAT cannot be solved by restricted proof systems.
4. Philosophical: finding a proof of a theorem feels genuinely harder than checking it.

Why proof of P ≠ NP is hard: Razborov and Rudich (1994) showed that a large class of techniques ("natural proofs") cannot prove P ≠ NP, assuming strong cryptographic assumptions. This is the "natural proofs barrier."

If P = NP:

• Every NP problem (including SAT, clique, vertex cover) has a poly-time algorithm.
• RSA, Diffie-Hellman, elliptic curve cryptography all collapse (since factoring and discrete log are in NP).
• AI could be automated: finding proofs would be as easy as checking them.
• Drug design, protein folding, scheduling — all tractable.

If P ≠ NP (expected):

• NP-complete problems have no polynomial-time exact algorithm.
• Modern cryptography is secure.
• The landscape of complexity classes (PSPACE, EXP, co-NP, PH, …) is rich and genuinely hierarchical.

The polynomial hierarchy (PH): NP is the first level. Σ_2^p = NP^NP (problems solvable by NP with an NP oracle). The full hierarchy PH = ∪_k Σ_k^p. If P = NP, the hierarchy collapses to P. If any level collapses, the whole hierarchy collapses.

PSPACE and EXP: PSPACE contains NP; EXP contains PSPACE. Both containments are believed (and for EXP, proven) to be strict. Complexity theory gives a rich map of computational difficulty, with NP-completeness as its most practically relevant landmark.

# Summary of complexity class relationships (as code comments)

# Known (proven):
#   P ⊆ NP ⊆ PSPACE ⊆ EXP
#   P ⊊ EXP  (time hierarchy theorem: more time => more power)
#   NP ⊊ EXP (also from hierarchy theorem)
#   P ⊊ PSPACE (space hierarchy + padding arguments)

# Believed but unproven:
#   P ⊊ NP  (the P vs. NP question)
#   NP ⊊ PSPACE
#   NP ≠ co-NP

# Implications of P = NP (proof by transitivity of reductions):
#   If SAT ∈ P, then for ALL L ∈ NP:
#       L ≤_p SAT  (by NP-hardness of SAT)
#       SAT ∈ P    (assumption)
#       => L ∈ P   (by upward closure of P under poly reductions)
#   => NP ⊆ P => P = NP

# Key complexity classes and representative complete problems:
classes = {
    "P":        "SORTING, SHORTEST-PATH, 2-SAT, PRIMES",
    "NP":       "SAT, CLIQUE, HAM-PATH, SUBSET-SUM, TSP-decision",
    "co-NP":    "TAUTOLOGY, GRAPH-NON-ISOMORPHISM",
    "PSPACE":   "QUANTIFIED-SAT (PSPACE-complete), GAME-EVALUATION",
    "EXP":      "GENERALIZED-CHESS, GENERALIZED-GO",
    "Undecidable": "HALTING-PROBLEM, VALIDITY-IN-ARITHMETIC",
}
for cls, examples in classes.items():
    print(f"{cls:15s}: {examples}")