Complexity in Computer Science (Thomas Watson)
LISTEN TO THIS EPISODE

Thomas Watson examines the capabilities and limits of efficient computation.
The discussion connects time and memory requirements with reductions, complexity classes, and P versus NP.
Randomness, hashing, error correction, and pseudorandomness reveal further ways to study computational resources.
The book extends these ideas to cryptography, learning, optimization, and verification.
Decision trees, communication protocols, and circuits provide concrete settings for understanding computational limits.
Corrections to the informal explanations: unbounded fan-in is finite for each circuit. BPP ⊆ P/poly follows from amplification and a union bound; the shifting argument concerns BPP ⊆ Σ₂P. PCP verification queries a specially encoded proof with bounded soundness error, rather than detecting almost any error from any three bits. The natural-proofs barrier assumes sufficiently strong pseudorandom functions; largeness means a non-negligible fraction of truth tables, and constructivity is measured in truth-table size. It does not rule out every approach to P versus NP. Amplification depends on the repetition count: 100 runs at error 1/3 do not ensure error below hardware-failure rates. Factoring concerns composite integers; randomly sampled strings can sometimes be compressible; heuristics may themselves use randomness. Path construction from reachability queries needs cycle avoidance.
Read about the original source: Complexity in Computer Science
Part of Marginalia: books, papers, and ideas for learning and debate.