
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.
Author: Thomas Watson
Source: Complexity in Computer Science · Thomas Watson
Series: AI & Computer Science · Book deep dive
Explore: AI & Computer Science
Related episodes: Backpropagation: Learning Representations by Back-Propagating Errors (Rumelhart, Hinton & Williams) · Yann LeCun & Randall Balestriero: The Platonic Representation Hypothesis with JEPAs
Flere episoder fra "Marginalia"



Gå ikke glip af nogen episoder af “Marginalia” - abonnér på podcasten med gratisapp GetPodcast.








