Short Notes

(a) Cook's Theorem (see Q86/Q72)

SAT is first NP-complete problem (1971 Cook-Levin). Every $L∈NP$ reduces to SAT via tableau encoding of nondet TM computation into poly-size CNF formula $φ_x$ with variables for tape/head/state over time steps $p(n)$. SAT∈NP via assignment verifier. Consequence: $P=NP ⇔ SAT∈P$; Karp reduced SAT to 21 other problems proving NP-completeness pervasive. Foundations of complexity and hardness proofs.

(b) Randomized Algorithms (see Q59/Q74)

Use random choices; types Las Vegas (always correct, random time, e.g., Randomized Quicksort expected $O(n\log n)$) vs Monte Carlo (bounded error, e.g., Miller-Rabin primality). Techniques: random sampling, hashing, random pivot. Expected time analysis via linearity of expectation. Power: avoid worst-case inputs, simple, often faster average. Derandomization open.

(c) Bin Packing (see Q99)

Items sizes $∈(0,1]$, bins capacity1, minimize bins — NP-hard (reduction from Partition). Heuristics: Next Fit (factor2, $O(n)$), First Fit & Best Fit (1.7 approx, $O(n\log n)$), First Fit Decreasing / Best Fit Decreasing sorted (11/9≈1.22 approx, best simple). Applications: cutting stock, memory allocation, scheduling. No PTAS with ratio <3/2 unless $P=NP$; but asymptotic PTAS exists.