Aaron Roth: worst-case complexity is a bad argument against building real AI
Aaroth · x · 2026-09-14
TTIC/UPenn theorist Aaron Roth pushes back on using complexity theory to argue that building "true" AI is impossible. He notes that even the simplest ML problem — training a linear classifier to minimize classification error — is NP-hard to approximate, yet worst-case hardness has proven a terrible guide: real-world statistical learning problems of this kind get solved reliably anyway. Applying such impossibility arguments today, he argues, means ignoring the evident success of AI and especially recent reasoning models.
Related event: Aaron Roth Debunks Worst-Case Complexity Arguments Against AI(3 posts)→
More from AGI Musings
- Researcher argues catching up to frontier AI costs less than proposed compute budgets — eliebakouch · 2026-09-14
- Even an AI disaster would just push progress behind closed doors, argues thread — yeastsplainer · 2026-09-14
- LeCun called out as 'not very smart': critics say JEPA can't deliver superintelligence at 1000 TPS — teortaxesTex · 2026-09-14
- The hidden tax of multimodal AI: lung cancer study questions cross-validation gains — bravo_abad · 2026-09-14
- New series "Mathematics in the age of AI" asks if math is in a crisis — elsleightholm · 2026-09-14
- New Handbook Chapter Analyzes Sociodigital Exploitation of Africa — ChinasaTOkolo · 2026-09-14