Teaching intro theory of computation in the AI era: NP-completeness isn't the end anymore
fortnow · x · 2026-10-24
Lance Fortnow (Illinois Tech) reflects on teaching Intro to Theory of Computation for the first time since 2016:
- NP-completeness is no longer a reason to give up: modern tools like SAT solvers, MIP and TSP heuristics often solve practical instances well, turning NP-completeness into a starting point rather than a dead end.
- Computation is harder to understand: with neural nets, like Turing machines, we can mostly only study input/output behavior — echoing Rice's theorem.
- He also notes new theorems since his first teaching stint (e.g. Immerman–Szelepcsényi).
The post follows a reader challenging his earlier prediction that AI could replace him as a teacher.
More from AGI Musings
- Inverted dark forest: the agent universe is full of potential allies — tszzl · 2026-10-24
- Pathway's Adrian: compute scaling alone won't deliver the next leap, architecture will — schwentker · 2026-10-24
- Three themes from Open Intelligence event: verification, agent markets, team memory — schwentker · 2026-10-24
- Transformer co-author bets on per-user alignment; PyTorch CTO says operators bear liability — schwentker · 2026-10-24
- AI's 'body' is a GPU box in theory, but inference is physically distributed in practice — jd_pressman · 2026-10-24
- Gary Marcus endorses Claude-generated table dissecting assumptions behind AI doom concerns — GaryMarcus · 2026-10-24