Computation as a Universal and Fundamental Concept

Tim Roughgarden

Every chapter in the course, with links to the moment it begins in the video and in the transcript. For topics across all courses, see the Topic Index.

Intro Computation and Its Limits

Welcome to the Series

▶︎ 0:00 transcript ↗︎

Can Computers Solve Everything?

▶︎ 0:34 transcript ↗︎

Clever Algorithmic Shortcuts

▶︎ 1:35 transcript ↗︎

Easy Problems vs Hard Problems

▶︎ 3:09 transcript ↗︎

The P versus NP Question

▶︎ 4:32 transcript ↗︎

Do New Technologies Change the Rules?

▶︎ 5:25 transcript ↗︎

Top 10 Reasons to Watch This Series

▶︎ 6:42 transcript ↗︎

#10: Turing and the Birth of Computer Science

▶︎ 7:19 transcript ↗︎

#9: A Cast of Legendary Thinkers

▶︎ 7:53 transcript ↗︎

#8-7: Surprising Truths About Complexity

▶︎ 8:38 transcript ↗︎

#6: Grade School Math Is Not Optimal

▶︎ 9:47 transcript ↗︎

#5: Funny Mathematician Stories

▶︎ 10:17 transcript ↗︎

#4: Computer Science's Fight for Respect

▶︎ 10:49 transcript ↗︎

#3: LLMs Change Nothing About These Limits

▶︎ 11:44 transcript ↗︎

#2: What Quantum Computers Actually Change

▶︎ 12:25 transcript ↗︎

#1: The Million-Dollar P vs NP Mystery

▶︎ 13:05 transcript ↗︎

Lecture 1 Is There Anything Computers Can't Do?

Computation as a Universal Mystery

▶︎ 0:01 transcript ↗︎

Alan Turing's Landmark 1936 Paper

▶︎ 0:46 transcript ↗︎

Computer Science Before Computers Existed

▶︎ 2:49 transcript ↗︎

Hilbert's Program and the Decision Problem

▶︎ 5:20 transcript ↗︎

Gödel Shatters the Dream of Completeness

▶︎ 8:17 transcript ↗︎

What Remained After Gödel?

▶︎ 9:55 transcript ↗︎

What Is a Turing Machine?

▶︎ 11:44 transcript ↗︎

Simple Machines, Infinite Power

▶︎ 15:27 transcript ↗︎

Problems No Computer Can Ever Solve

▶︎ 17:47 transcript ↗︎

The Halting Problem Explained

▶︎ 21:12 transcript ↗︎

Why the Halting Problem Is Unsolvable

▶︎ 25:57 transcript ↗︎

Step 1: The Universal Turing Machine

▶︎ 28:35 transcript ↗︎

Why Computer Science Is a Real Discipline

▶︎ 33:23 transcript ↗︎

Step 2: The Diagonalization Trick

▶︎ 36:03 transcript ↗︎

Step 3: Reductions Spread Impossibility

▶︎ 40:47 transcript ↗︎

Can Anything Beat a Turing Machine?

▶︎ 48:00 transcript ↗︎

Church's Lambda Calculus and Turing-Completeness

▶︎ 53:17 transcript ↗︎

The Eccentric Blackboard Ritual

▶︎ 55:07 transcript ↗︎

Lecture 2 How Algorithms Outsmart Complexity

Algorithms Are Recipes for Problem Solving

▶︎ 0:00 transcript ↗︎

A 23-Year-Old Disproves a Famous Conjecture

▶︎ 3:11 transcript ↗︎

How Grade School Multiplication Works

▶︎ 6:48 transcript ↗︎

Recursion: Solving Big Problems with Small Ones

▶︎ 10:49 transcript ↗︎

Splitting Numbers Into Smaller Multiplications

▶︎ 13:52 transcript ↗︎

The Key Insight: Reuse Instead of Redo

▶︎ 17:50 transcript ↗︎

The Eureka Trick That Saves a Multiplication

▶︎ 21:46 transcript ↗︎

Step-by-Step Faster Multiplication

▶︎ 24:02 transcript ↗︎

Why This Matters: From Python to Matrices

▶︎ 26:41 transcript ↗︎

Finding the Shortest Path in a Network

▶︎ 30:43 transcript ↗︎

Why Checking Every Option Fails

▶︎ 33:55 transcript ↗︎

Exponential Growth and Atoms in the Universe

▶︎ 39:40 transcript ↗︎

Dijkstra's Algorithm: The Expanding Balloon

▶︎ 43:45 transcript ↗︎

The Golden Era of Algorithm Design

▶︎ 48:46 transcript ↗︎

The Homework Legend That Was Actually True

▶︎ 50:09 transcript ↗︎

When Von Neumann Discovered Duality in Real Time

▶︎ 52:45 transcript ↗︎

When Algorithms Hit a Wall: Enter P vs NP

▶︎ 55:44 transcript ↗︎

Lecture 3 Easy Problems, Hard Problems

Recap: Shortest Paths and Algorithmic Shortcuts

▶︎ 0:00 transcript ↗︎

Do Algorithmic Shortcuts Always Exist?

▶︎ 2:43 transcript ↗︎

The Traveling Salesman Problem Explained

▶︎ 4:08 transcript ↗︎

TSP: Solvable But Not Efficiently

▶︎ 7:18 transcript ↗︎

A Bold Conjecture and the Road to P vs NP

▶︎ 10:11 transcript ↗︎

What Makes a Problem Easy to Solve?

▶︎ 12:54 transcript ↗︎

Polynomial-Time Algorithms Defined

▶︎ 16:31 transcript ↗︎

Moore's Law: Polynomial vs Exponential Growth

▶︎ 19:16 transcript ↗︎

The Class P and Its Connection to Turing

▶︎ 24:06 transcript ↗︎

NP-Completeness: The Idea of Relative Hardness

▶︎ 26:36 transcript ↗︎

NP Problems: Easy to Check, Hard to Solve

▶︎ 32:54 transcript ↗︎

Universal Problems That Encode Everything

▶︎ 35:28 transcript ↗︎

Two Possible Worlds: P = NP or P ≠ NP

▶︎ 39:09 transcript ↗︎

Reductions: Proving One Problem Is As Hard

▶︎ 47:10 transcript ↗︎

The Cook-Levin Theorem: NP-Completeness Exists

▶︎ 54:04 transcript ↗︎

Tenacity in Research: Stories of Cook and Levin

▶︎ 57:01 transcript ↗︎

Lecture 4 Two Worlds We Might Live In

Recap: Easy Problems, Hard Problems, and Shared Fate

▶︎ 0:01 transcript ↗︎

Two Themes: Power and Limitations of Computation

▶︎ 3:17 transcript ↗︎

Historical Backdrop: Algorithms vs Lower Bounds

▶︎ 5:47 transcript ↗︎

Engineering Mindset vs Pure Math Mindset

▶︎ 8:20 transcript ↗︎

Classifying Our Cast of Characters

▶︎ 11:30 transcript ↗︎

Karp's 21 Problems: The Big Bang of NP-Completeness

▶︎ 19:41 transcript ↗︎

How NP-Completeness Changed Everything

▶︎ 26:16 transcript ↗︎

Meeting the Pioneers of NP-Completeness

▶︎ 28:20 transcript ↗︎

Visualizing the Two Possible Worlds

▶︎ 29:10 transcript ↗︎

The P vs NP Question Formally Stated

▶︎ 32:01 transcript ↗︎

Millennium Prize: A Million Dollar Question

▶︎ 33:46 transcript ↗︎

What Do P, NP, and NP-Complete Actually Mean?

▶︎ 36:55 transcript ↗︎

Naming NP-Complete: Hardass or Hard-Boiled?

▶︎ 40:25 transcript ↗︎

Why Experts Bet on P ≠ NP

▶︎ 43:45 transcript ↗︎

The Vibes Argument: It Just Feels True

▶︎ 48:36 transcript ↗︎

Why Proving P ≠ NP Is Nearly Impossible

▶︎ 49:37 transcript ↗︎

Will We Ever Solve P vs NP?

▶︎ 52:57 transcript ↗︎

Lecture 5 AI, Quantum Computing, and Beyond

Recap: The P vs NP Question

▶︎ 0:01 transcript ↗︎

NP-Intermediate Problems and Ladner's Theorem

▶︎ 3:24 transcript ↗︎

Factoring: The Problem Behind Your Encryption

▶︎ 5:48 transcript ↗︎

Graph Isomorphism: Are Two Networks the Same?

▶︎ 8:35 transcript ↗︎

Why Levin Had Bad Luck and Karp Didn't

▶︎ 10:57 transcript ↗︎

What If We Prove P ≠ NP?

▶︎ 17:09 transcript ↗︎

What If P = NP With Fast Algorithms?

▶︎ 22:03 transcript ↗︎

The Awkward Scenario: P = NP But No Useful Code

▶︎ 25:53 transcript ↗︎

When Definitions Need an Upgrade

▶︎ 30:51 transcript ↗︎

Do New Technologies Challenge Computation?

▶︎ 34:12 transcript ↗︎

Quantum Computing vs the Extended Thesis

▶︎ 39:42 transcript ↗︎

Shor's Algorithm: Quantum Computers Break RSA

▶︎ 42:01 transcript ↗︎

Post-Quantum Cryptography to the Rescue

▶︎ 45:00 transcript ↗︎

Revising the Extended Church-Turing Thesis

▶︎ 46:19 transcript ↗︎

Can AI Overcome Fundamental Limits?

▶︎ 49:43 transcript ↗︎

Secrets Behind LLM Performance

▶︎ 53:35 transcript ↗︎

How AI Creates the Illusion of Solving Everything

▶︎ 58:54 transcript ↗︎

Computation Transcends All Technology

▶︎ 1:03:49 transcript ↗︎