Complexity Theory — P, NP, and NP-Completeness

Complexity Theory asks: among all decidable problems, which ones can be solved EFFICIENTLY? "Efficiently" means polynomial time — O(nᵏ) for some constant k.

Time Complexity Classes:

P (Polynomial Time):
Problems solvable by a deterministic TM in O(nᵏ) time. These are the "tractable" problems — practically solvable even for large inputs.
Examples: sorting, shortest path, primality testing (AKS algorithm, 2002), matrix multiplication, most graph algorithms.

NP (Nondeterministic Polynomial Time):
Two equivalent definitions:
① Problems solvable by a NONDETERMINISTIC TM in polynomial time (the machine "guesses" the solution)
② Problems where a given solution can be VERIFIED in polynomial time
Key insight: verifying is often much easier than finding. Given a proposed Hamiltonian cycle, you can verify it in O(n). Finding one might take exponential time.

Examples: Boolean Satisfiability (SAT), Traveling Salesman, Graph Coloring, Subset Sum, Knapsack.

P ⊆ NP (trivially: if you can solve it, you can verify it). The million-dollar question: P = NP?

NP-Hard: problems at least as hard as the hardest NP problems. Solving any NP-Hard problem in poly-time would solve ALL NP problems.

NP-Complete: NP-Hard AND in NP. The hardest problems IN NP.
- Cook-Levin Theorem (1971): SAT is NP-Complete. FIRST proof.
- After SAT, proving other problems NP-Complete: reduce SAT to your problem in poly time.
- If your problem X is NP-Complete: don't search for poly-time algorithm (likely doesn't exist). Use approximation, heuristics, or exact algorithms for small inputs.

Polynomial Reduction (A ≤p B):
"A reduces to B in poly time" means: solve A by transforming input to B's input, solve B, transform output. If B ∈ P and A ≤p B, then A ∈ P. Reductions prove relative hardness.

Important NP-Complete problems:
- SAT: given boolean formula, is there an assignment making it true?
- 3-SAT: SAT where formula is in 3-CNF (at most 3 literals per clause). Everything reduces to 3-SAT.
- Vertex Cover: find minimum set of vertices covering all edges
- Clique: does graph have clique of size k?
- Hamiltonian Path/Cycle: visit all vertices exactly once
- TSP (decision): is there a tour of cost ≤ k?
- Graph Coloring: color graph with k colors, no adjacent same color
- Subset Sum: does subset sum to target T?
- Partition: can set be divided into two equal-sum subsets?

Beyond NP:
- co-NP: complements of NP problems (UNSAT — prove formula has no solution)
- PSPACE: decidable using polynomial SPACE (may use exponential time)
- EXPTIME: decidable in exponential time
- Undecidable: no algorithm at all

Why P≠NP is believed (but unproven):
- Thousands of smart people tried for 50+ years — no poly-time algorithm found for any NP-Complete problem
- Cryptography depends on it (RSA, factoring assumed hard)
- But absence of evidence is not evidence of absence — it could be proven tomorrow

1import time
2import random
3import itertools
4
5# ── P problems: polynomial time ────────────────────────
6print("=== P Problems (polynomial time) ===
7")
8
9def is_prime_miller_rabin(n, k=10):
10    """Miller-Rabin primality test — O(k log²n) — polynomial!"""
11    if n < 2: return False
12    if n == 2: return True
13    if n % 2 == 0: return False
14    r, d = 0, n - 1
15    while d % 2 == 0:
16        r += 1
17        d //= 2
18    for _ in range(k):
19        a = random.randrange(2, n - 1)
20        x = pow(a, d, n)
21        if x == 1 or x == n - 1: continue
22        for _ in range(r - 1):
23            x = pow(x, 2, n)
24            if x == n - 1: break
25        else:
26            return False
27    return True
28
29large_prime = 2**61 - 1   # Mersenne prime
30start = time.perf_counter()
31result = is_prime_miller_rabin(large_prime)
32elapsed = time.perf_counter() - start
33print(f"Is 2^61-1 prime? {result} (took {elapsed*1000:.2f}ms) — P problem")
34
35# Shortest path (Dijkstra) — O(E log V)
36import heapq
37def dijkstra(graph, start):
38    dist = {v: float('inf') for v in graph}
39    dist[start] = 0
40    pq = [(0, start)]
41    while pq:
42        d, u = heapq.heappop(pq)
43        if d > dist[u]: continue
44        for v, w in graph[u]:
45            if dist[u] + w < dist[v]:
46                dist[v] = dist[u] + w
47                heapq.heappush(pq, (dist[v], v))
48    return dist
49
50graph = {0:[(1,4),(2,1)], 1:[(3,1)], 2:[(1,2),(3,5)], 3:[]}
51print(f"Shortest paths from 0: {dijkstra(graph, 0)} — P problem")
52
53# ── NP problem: SAT ────────────────────────────────────
54print("
55=== NP Problem: Boolean SAT ===
56")
57
58def sat_brute_force(clauses, n_vars):
59    """
60    clauses: list of lists of literals (positive int = var, negative = NOT var)
61    Exponential O(2^n) — but solutions easy to VERIFY in O(n)
62    """
63    for assignment in itertools.product([False,True], repeat=n_vars):
64        satisfied = True
65        for clause in clauses:
66            clause_sat = False
67            for lit in clause:
68                var = abs(lit) - 1
69                val = assignment[var]
70                if lit < 0: val = not val
71                if val:
72                    clause_sat = True
73                    break
74            if not clause_sat:
75                satisfied = False
76                break
77        if satisfied:
78            return assignment
79    return None
80
81# (x1 OR x2) AND (NOT x1 OR x3) AND (NOT x2 OR NOT x3)
82clauses = [[1,2], [-1,3], [-2,-3]]
83result = sat_brute_force(clauses, 3)
84print(f"SAT instance: (x1∨x2)∧(¬x1∨x3)∧(¬x2∨¬x3)")
85if result:
86    x1,x2,x3 = result
87    print(f"Satisfying assignment: x1={x1} x2={x2} x3={x3}")
88    # Verify (polynomial time!)
89    verify = all(
90        any((assignment[abs(l)-1] if l>0 else not assignment[abs(l)-1])
91            for l in clause)
92        for clause, assignment in [(c, result) for c in clauses]
93    )
94    print(f"Verified: {verify} ✓  ← verification is O(n), finding was O(2^n)")
95
96# ── NP-Hard: TSP exact solution ────────────────────────
97print("
98=== NP-Hard: Traveling Salesman (exact) ===
99")
100
101def tsp_exact(distances):
102    n = len(distances)
103    cities = list(range(n))
104    best_cost = float('inf')
105    best_path = None
106    count = 0
107    for perm in itertools.permutations(cities[1:]):
108        path = [0] + list(perm) + [0]
109        cost = sum(distances[path[i]][path[i+1]] for i in range(n))
110        count += 1
111        if cost < best_cost:
112            best_cost = cost
113            best_path = path
114    return best_path, best_cost, count
115
116dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
117n = len(dist)
118start = time.perf_counter()
119path, cost, perms = tsp_exact(dist)
120elapsed = time.perf_counter() - start
121print(f"4-city TSP: best path={path} cost={cost}")
122print(f"Checked {perms} permutations in {elapsed*1000:.2f}ms")
123print(f"For n=20 cities: {20*19*18*17*16:,} permutations → intractable!")
124
125print("
126Key insight:")
127print("  P:           Can FIND solution in polynomial time")
128print("  NP:          Can VERIFY solution in polynomial time")
129print("  NP-Complete: Hardest in NP (all NP reduces to these)")
130print("  P = NP?      Unknown — Millennium Prize Problem ($1M)")