Fortnow: why formalizing complexity results in Lean is hard — proving polynomial time
fortnow · x · 2026-10-16
Complexity theorist Lance Fortnow explains why some results from the OpenAI Math Drop (including L = RL = BPL) lack Lean proofs.
Using Lautemann's proof that BPP ⊆ Σ₂ᵖ as an example: the probabilistic argument is not too hard for Claude to formalize, though Lean forces you to handle details papers wave away (e.g. nᵏ·2⁻ⁿ < 1). The real bottleneck is showing algorithms actually run in polynomial time — painfully obvious-on-paper statements like computing the disjunction in polynomial time turn out to be the hardest part to formalize in Lean.
More from Research
- DIY benchmark ranks 18 models on subjective judgments, GLM-5.3 tops consensus match — arkuto · 2026-10-16
- UCSD Researchers Propose Dataset Watermarking Detectable via Black-Box API Access — yuxiangw_cs · 2026-10-16
- EmbodiedEvo tops RoboDojo as agents inherit reusable skills and lessons — Aiden_Tech_Ai · 2026-10-16
- CHI reviewer laments: papers' Discussion sections now cite nothing — IanArawjo · 2026-10-16
- Casper: Understanding 90% of neurons ≠ understanding the network — StephenLCasper · 2026-10-16
- NVIDIA Launches cuPotential in CUDA-X to Bring AI Agents to Semiconductor Materials Simulation — tomaszbednarz · 2026-10-16