算法详解系列图书共有4卷，本书是第4卷——NP-Hard问题算法。全书共有6章，主要介绍了快速识别NP-Hard问题的方法和处理NP的算法工具。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。
本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维与计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。
第1章 什么是NP问题
1.1 MST和TSP：算法的难解之谜
1.1.1 最小生成树问题
1.1.2 旅行商问题
1.1.3 解决TSP的尝试和失败
1.1.4 小测验1.1–1.2的答案
1.2 读者的不同专业层次
1.3 容易的问题和困难的问题
1.3.1 多项式时间的算法
1.3.2 多项式时间与指数级时间
1.3.3 容易的问题
1.3.4 相对难以处理
1.3.5 困难的问题
1.3.6 P≠NP猜想
1.3.7 NP问题的临时定义
1.3.8 随机化和量子算法
1.3.9 微妙性
1.4 NP问题的算法策略
1.4.1 通用、正确、快速（选择其二）
1.4.2 通用性的妥协
1.4.3 正确性的妥协
1.4.4 最坏情况运行时间的妥协
1.4.5 关键思路
1.5 证明NP问题：一个简单的方案
1.5.1 转化
1.5.2 使用转化来设计快速算法
1.5.3 使用转化对NP问题进行扩展
1.5.4 无环最短短路径是NP问题
1.5.5 小测验1.3的答案
1.6 新手错误和可接受的不准确说法
1.7 本章要点
1.8 章末习题
1.8.1 挑战题
1.8.2 编程题
第2章 正确性的妥协：高效的不准确算法
2.1 完成工时最小化
2.1.1 问题定义
2.1.2 贪心算法
2.1.3 Graham算法
2.1.4 运行时间
2.1.5 近似的正确性
2.1.6 定理2.1的证明
2.1.7 处理时间优先（LPT）
……
第3章 速度的妥协：准确的非高效算法
第4章 证明NP问题
第5章 P、NP及相关概念
第6章 案例研究：FCC激励拍卖
后记 算法设计实战指南
附录 问题提示和答案
蒂姆·拉夫加登（Tim Roughgarden），哥伦比亚大学计算机科学系教授，之前曾任教于斯坦福大学，主要研究领域包括算法、博弈论以及微观经济学。他曾获得美国青年科学家与工程师总统奖（PECASE），ACM颁发的Grace Murray Hopper奖，Game Theory Society颁发的Kalai奖，Mathematical Programming Society颁发的Tucker奖，以及EATCS-SIGACT颁发的G?del奖。
