P24 · P-class showcase

🔊 Listen

1 · What P contains · the three classic showcases

P = ⋃_k TIME(n^k) — the union over all k of "decidable in O(n^k) time." Sipser's three flagship examples (§7.2) cover the three flavors of "polynomial":

PATH = {⟨G, s, t⟩ : G has a directed path from s to t}

Algorithm: BFS from s; mark every reachable vertex. Accept iff t is marked.

Time: O(V + E). Linear in the graph size — about as fast as polynomial gets.

RELPRIME = {⟨a, b⟩ : gcd(a, b) = 1}

Algorithm: Euclid's algorithm — repeatedly replace (a, b) with (b, a mod b) until b = 0; gcd is the final a.

Time: O(log min(a, b)) iterations. Polynomial in bit length, which is what matters.

A_CFG = {⟨G, w⟩ : CFG G generates w}

Algorithm: convert G to CNF; run CYK dynamic programming.

Time: O(n³ · |G|). Cubic — slower than the others but still polynomial.

🔊 Listen

2 · Why these are in P · the contrast with NP-hard cousins

The shift is often a single quantifier or a "for all/exists every" change. PATH asks any s-t path — easy. HAMPATH asks a path visiting every vertex — combinatorially hard. A_DFA simulates one machine — easy. SAT asks for an assignment that satisfies every clause — hard.

🔊 Listen

3 · Animated demo · auto-plays · loops

🔊 Listen

4 · Pitfalls

"Polynomial" is polynomial in input size, not the value being computed. RELPRIME runs in O(log min(a, b)) iterations — polynomial in the bit length of a and b, exponential in their value. Always polynomial in n = |input|.
O(n³) is polynomial, period. Sometimes seen as "slow polynomial." Still in P. The hierarchy P ⊆ TIME(n³) ⊆ … is internal to P; all of it is P.
Adjacency-list vs adjacency-matrix matters for big-O constants. PATH's O(V + E) assumes adjacency-list representation; matrix gives O(V²). Both are polynomial.
Membership in P doesn't mean tractable in practice. A polynomial with degree 100 and large constants might be infeasible. The mathematical class P is the right abstraction; engineering needs constants.

🔊 Listen

5 · Q&A defence notes

Q1. Why is PATH in P but HAMPATH probably not?
PATH asks "does ANY directed path from s to t exist" — solvable by BFS in O(V + E). HAMPATH asks "does a path through ALL vertices, ending at t, exist" — combinatorial search through n! permutations. The existential quantifier in PATH is satisfied locally; in HAMPATH it requires global coordination.
Q2. Why is Euclid's gcd algorithm fast?
Each step at least halves the smaller number (provable: a mod b < b/2 when a ≥ b). So O(log min(a, b)) iterations are needed. With O(n²) per multiplication, total is O(n³) in bit length n.
Q3. Why O(n³) for CYK?
CYK's DP table has O(n²) cells (start position × length). Computing each cell tries O(n) split points. Total cells × splits = O(n³). Plus the constant grammar factor.
Q4. What's the biggest open problem about P?
P vs NP — whether NP-complete problems like SAT, HAMPATH have polynomial-time algorithms. Most computer scientists believe P ≠ NP, but no proof is known. One of the Clay Millennium Problems with a $1M prize.

🔊 Listen

6 · Where to read more

Sipser: §7.2 (the three classic examples), Theorem 7.14, 7.15, 7.16. Lecture notes: Module 4 slide 5. Companion problems: P12 (decidable trio), P17 (growth race), P48 (P vs EXPTIME).