Theory of Computation I

on YouTube ↗01h 01m

" summary

Overview mixes history and concrete results: 1936 Turing machine definition and the proof that some simple problems are unsolvable; von Neumann’s 1946 architecture; Strassen’s trick that beats n^3 matrix multiply; randomized primality tests contrasted with hard factoring; Erdos–Rényi random graph statistics; the multiplicative weights algorithm with provable regret bounds; and the central P vs NP framing with reductions.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 3:36Alan M. Turing (1912-1954)
3. 5:55The Turing machine
4. 8:39The halting problem
5. 9:591946: Turing's idea becomes reality
6. 14:42Computer Science 1946-2018: We've come a long way
7. 17:13Fast algorithms
8. 21:43Randomness is our friend!
9. 28:13By the way, random graphs are our friends too
10. 31:24Back to primality being easy
11. 32:12On the subject of Complexity: a bunch of numbers
12. 33:58Matching boys and girls and pets?
13. 34:47The Facebook network
14. 35:49Another puzzle: the set cover problem
15. 36:52Not so obvious: Number splitting and matching are related!
16. 38:21NP-completeness FAQ
17. 50:18YES! The multiplicative weights