P vs NP &
NP-Completeness

Optimization turns into decision with a budget k. Binary search on k recovers the optimum.

That is why theory can focus on yes/no questions without losing anything.

Caveat: n¹⁰⁰ is in P but useless. 1.0001ⁿ is not in P but fine for small n.

Common mistake: "exponential" means the exponent grows with n. n⁵⁰ is polynomial. 2^√n is not polynomial, but it is sub-exponential.

• Completeness. Every yes-instance has some short proof that V accepts.
• Soundness. No no-instance has any proof that V accepts.
• Only yes-answers need proofs. That asymmetry leads to co-NP.

NP stands for Nondeterministic Polynomial time, not "non-polynomial".

P = NP?  ⇔  "Can checking always be turned into finding?"

def verify_sat(cnf, assignment):
    """cnf: list of clauses, each a list of non-zero ints (DIMACS style).
    assignment: dict var -> bool. Runs in O(size of formula)."""
    return all(any(assignment[abs(l)] == (l > 0) for l in clause)
               for clause in cnf)

# (x1 v -x2 v x3) ^ (-x1 v x2) ^ (x2 v x3) ^ (-x3 v -x1)
cnf = [[1, -2, 3], [-1, 2], [2, 3], [-3, -1]]
print(verify_sat(cnf, {1: False, 2: True, 3: True}))
print(verify_sat(cnf, {1: True, 2: False, 3: False}))

True
False

Linear time in the formula. Finding that assignment may take up to 2ⁿ tries.

import itertools

def verify_clique(edges, k, S):
    S = set(S)
    return len(S) >= k and all(
        (u, v) in edges or (v, u) in edges
        for u, v in itertools.combinations(S, 2))

def verify_subset_sum(nums, target, idx):
    return (len(set(idx)) == len(idx)
            and sum(nums[i] for i in idx) == target)

E = {(1, 2), (1, 3), (2, 3), (3, 4)}
assert verify_clique(E, 3, [1, 2, 3])
assert not verify_clique(E, 3, [2, 3, 4])
assert verify_subset_sum([3, 34, 4, 12, 5, 2], 9, [2, 4])

Proof. Compute f(x) in p(n) time. So |f(x)| ≤ p(n). Run B's q-time decider on it. Total time: p(n) + q(p(n)), still a polynomial. □

Transitive. A ≤_p B ≤_p C ⇒ A ≤_p C. Just compose the maps.

NP-hard means "at least as hard as NP". It can be far harder, even undecidable.

Halting is NP-hard: map φ to a program that tries all assignments and halts iff it finds one.

SAT ∈ NP: the assignment is the certificate. Hardness is the real work. Take any L ∈ NP with an NTM M running in T = n^k steps. Build a formula φ_x that is satisfiable iff M accepts x.

φ_x = φ_cell ∧ φ_start ∧ φ_move ∧ φ_accept

First turn any formula into CNF in poly time with Tseitin encoding (a new variable per gate). Then split each clause into 3-literal clauses:

(ℓ₁∨ℓ₂∨…∨ℓ_k)  ↦

(ℓ₁∨ℓ₂∨y₁)(¬y₁∨ℓ₃∨y₂)…(¬y_k−3∨ℓ_k−1∨ℓ_k)

Map: for a 3-CNF φ with m clauses, build graph G:

• One vertex per literal occurrence: 3m vertices.
• A triangle on each clause's three vertices.
• A conflict edge between every x and ¬x.
• Ask: does G have an independent set of size k = m?

Map size is O(m²) edges at most. So it runs in poly time.

def sat3_to_is(cnf):
    """One vertex per literal occurrence. Triangle inside each clause,
    edge between complementary literals. Satisfiable <=> IS of size m."""
    V = [(ci, l) for ci, c in enumerate(cnf) for l in c]
    E = set()
    for a, b in itertools.combinations(V, 2):
        same_clause = a[0] == b[0]
        conflict = a[1] == -b[1]
        if same_clause or conflict:
            E.add((a, b))
    return V, E, len(cnf)

f = [[1, 2, -3], [-1, 3, 2], [-2, -3, 1]]
V, E, k = sat3_to_is(f)
print(len(V), "vertices,", len(E), "edges, need IS of size", k,
      "->", has_is(V, E, k))

9 vertices, 15 edges, need IS of size 3 -> True

def has_is(V, E, k):          # brute force, only for testing
    adj = {v: set() for v in V}
    for a, b in E: adj[a].add(b); adj[b].add(a)
    for S in itertools.combinations(V, k):
        if all(b not in adj[a]
               for a, b in itertools.combinations(S, 2)):
            return True
    return False

# property test: reduction agrees with brute-force SAT
for _ in range(60):
    n = rng.randint(3, 5)
    f = random_3sat(n, rng.randint(2, 6), rng)
    V, E, k = sat3_to_is(f)
    assert has_is(V, E, k) == (brute_sat(f, n) is not None)

Proof (VC). An edge uv is uncovered by V−S iff both ends are in S. That is iff S is not independent. □

These maps are trivial, but hardness flows through them. One NP-complete member makes all three NP-complete.

Step 1. CLIQUE ∈ NP. The certificate is the k vertices. Check all C(k,2) pairs: O(k²) time.

Step 2. Pick a known NP-complete problem. IS, proved from 3SAT a few slides back.

Step 3. Build the map. f(G, k) = (Ḡ, k). Flip every pair: edge ↔ non-edge. O(n²) time.

Step 4. Yes ⇒ yes. If S is an IS in G, no pair in S is an edge of G. So every pair is an edge of Ḡ. S is a clique in Ḡ.

Step 5. Yes ⇐ yes. Same argument backwards. A clique in Ḡ is an IS in G.

Step 6. Conclude. IS ≤_p CLIQUE, and CLIQUE ∈ NP. So CLIQUE is NP-complete. □

def verify_clique(adj, k, S):             # certificate S: the k vertices
    return len(set(S)) >= k and all(v in adj[u] for u, v in combinations(S, 2))

def is_to_clique(adj, k):                 # (G, k) -> (complement of G, k)
    V = list(adj)
    comp = {u: {v for v in V if v != u and v not in adj[u]} for u in V}
    return comp, k

# G = the 6-vertex graph from the last slide
H, k = is_to_clique(G, 3)
print("clique {a,d,f} in complement:", verify_clique(H, 3, "adf"))
print("clique {a,b,c} in complement:", verify_clique(H, 3, "abc"))

clique {a,d,f} in complement: True
clique {a,b,c} in complement: False

IS {a, d, f} in G became a clique in Ḡ. G has 7 edges, so Ḡ has 15 − 7 = 8.

φ = C₁ ∧ C₂, with C₁ = (x₁ ∨ ¬x₂ ∨ x₃) and C₂ = (¬x₁ ∨ x₂ ∨ x₃).

Row v_i has a 1 in clause column j iff literal x_i is in C_j. Row v_i' does the same for ¬x_i.

  10010   v1
+ 01001   v2
+ 00100   v3'
= 11111   each clause has 1 true literal
+ 00033   s1 + s1' + s2 + s2'
= 11144   target hit

subsets hitting target: 6   satisfying assignments: 6

Checked by brute force in Python. Common mistake: using only one slack per clause. Then a clause with 1 true literal can only reach 2, and the map breaks.

def brute_sat(cnf, n):
    for bits in itertools.product([False, True], repeat=n):
        a = {i + 1: bits[i] for i in range(n)}
        if verify_sat(cnf, a):
            return a
    return None
def simplify(cnf, assign):
    out = []
    for c in cnf:
        if any(assign.get(abs(l)) == (l > 0) for l in c):
            continue                             # clause already true
        rest = [l for l in c if abs(l) not in assign]
        if not rest: return None                 # clause false: conflict
        out.append(rest)
    return out
def dpll(cnf, assign=None):
    assign = dict(assign or {})
    while True:                               # unit propagation
        cnf = simplify(cnf, assign)
        if cnf is None: return None
        if not cnf: return assign
        unit = next((c[0] for c in cnf if len(c) == 1), None)
        if unit is None: break
        assign[abs(unit)] = unit > 0
    lit = cnf[0][0]                           # branch
    for val in (lit > 0, lit < 0):
        res = dpll(cnf, {**assign, abs(lit): val})
        if res is not None: return res
    return None

Random 3-SAT with m = 4.26n clauses (the hardest ratio). Mean of 3 formulas per size:

n   brute(s)   dpll(s)
10     0.0023    0.0002
14     0.0263    0.0004
18     0.8263    0.0016
20     1.9263    0.0018

• Brute force tries up to 2ⁿ assignments. It grows about 1000× from n=10 to n=20.
• Unit propagation spots forced values and prunes huge subtrees. DPLL is about 1000× faster at n=20 here.
• DPLL is still exponential in the worst case. Pigeonhole formulas need 2^Ω(n) steps for any DPLL run (Haken 1985).

Cross-checked: brute force and DPLL agree on 300 random formulas, and every DPLL answer passes verify_sat.

MiniSat, Glucose, CaDiCaL, Kissat. They routinely solve industrial formulas with millions of variables.

def subset_sum(nums, T):
    reach = 1                       # bit i set <=> sum i reachable
    for x in nums:
        reach |= reach << x         # take x, or don't
    return bool(reach >> T & 1)

print(subset_sum([3, 34, 4, 12, 5, 2], 9),
      subset_sum([3, 34, 4, 12, 5, 2], 30))

True False

This is the classic DP table packed into one Python big-int. It takes O(n·T) bit operations.

Weakly NP-complete problems often have an FPTAS (a fully polynomial approximation scheme). Knapsack can be solved to within (1−ε) in poly(n, 1/ε) time.

This drawing assumes every inclusion is strict. Only P ≠ EXP is proven (time hierarchy theorem).

• UNSAT: "φ has no satisfying assignment." What short proof shows that? None is known.
• Factoring is in NP ∩ co-NP. The prime factorization certifies either answer, and PRIMES is in P.
• If an NP-complete problem is in co-NP, then NP = co-NP.
• P = NP ⇒ NP = co-NP, since P is closed under complement.

At least one inclusion in P ⊆ NP ⊆ PSPACE ⊆ EXP is strict. We don't know which one.

Impagliazzo's "five worlds" (1995): Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania. They describe what the world looks like under each answer.

def vc_2approx(edges):
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:
            cover |= {u, v}        # edge uncovered: take both ends
    return cover

# 200 random graphs on 8 nodes vs brute-force optimum
worst = 0
for _ in range(200):
    edges = [(u, v) for u, v in itertools.combinations(range(8), 2)
             if rng.random() < .3]
    a, o = vc_2approx(edges), vc_opt(range(8), edges)
    assert len(a) <= 2 * len(o)
    if o: worst = max(worst, len(a) / len(o))
print("worst ratio seen:", round(worst, 2))

worst ratio seen: 2.0

The bound is tight. A single edge is enough: ALG picks 2 vertices, while OPT needs only 1.

Decision rule. Small n: go exact. Small parameter: FPT. Need a guarantee: approximate. Huge and messy: heuristics or a solver.