Demaine 等出新书《Computational Intractability》，续写 Garey-Johnson 经典

fortnow · x · 2026-11-10

Erik Demaine、Bill Gasarch 与 Mohammad Hajiaghayi 合著的新书《Computational Intractability: A Guide to Algorithmic Lower Bounds》出版，被视为 1979 年 Garey & Johnson 经典《Computers and Intractability》的续篇。全书超 500 页仍未能穷尽 1979 年以来的进展，覆盖 P/NP、大量 NP 完全问题证明，包括圆盘装箱（强 NP-hard）、卡坦岛「一步将杀」（NP-complete）、必输跳棋，以及超级马里奥等任天堂游戏的关卡可达性等趣味案例。Lance Fortnow 与 Gasarch 在博客中对谈介绍了本书。