Demaine-Gasarch-Hajiaghayi publish 500-page sequel to Garey & Johnson's NP-completeness classic
fortnow · x · 2026-11-10
Erik Demaine, Bill Gasarch, and Mohammad Hajiaghayi published "Computational Intractability: A Guide to Algorithmic Lower Bounds," a sequel to the 1979 Garey & Johnson classic. Over 500 pages yet still not covering everything since 1979, it spans P/NP and many NP-completeness proofs, including disk packing (strongly NP-hard), Catan mate-in-1, losing checkers, and level-reachability in Super Mario Bros. and other Nintendo games. Lance Fortnow interviewed Gasarch about it on the Computational Complexity blog.
More from Research
- Chris McIntosh named Lead AI Scientist at UHN's Peter Munk Cardiac Care Centre — VectorInst · 2026-11-10
- Vector team wins MICCAI 2026 pediatric brain tumor segmentation challenge — VectorInst · 2026-11-10
- Benjamin Haibe-Kains wins community award for open science in AI drug discovery — VectorInst · 2026-11-10
- Nicolas Papernot wins 2026 NSERC McDonald Fellowship for trustworthy AI foundations — VectorInst · 2026-11-10
- Kieran Campbell wins CSMB New Investigator Award for ML in single-cell and cancer genomics — VectorInst · 2026-11-10
- Medical foundation model study for prostate cancer wins MICCAI IJCARS Best Paper Award — VectorInst · 2026-11-10