目录 1
第1章 基础概念 1
§1.1 问题的难易性，复杂度的直观概念 1
§1.2 确定型图灵机与P类，基于图灵机的复杂度概念 14
§1.3 非确定型计算与NP类，P与NP的关系 31
§1.4 多项式变换、NPC类与Cook定理 40
第2章 证明问题属于NPC类的方法 55
§2.1 基本的和常见的NPC问题 55
§2.2 关于NPC的证明方法 81
第3章 P与NPC的分界，证明问题属于P类的方法 96
§3.1 P类问题与NPC类问题的分界 96
§3.2 证明问题属于P类的例 98
第4章 对付NPC问题的办法 124
§4.1 近似算法 124
§4.2 概率算法 181
第5章 NP类的结构及进一步的知识 203
§5.1 NP的结构 203
§5.2 CO-NP类 204
§5.3 伪多项式时间算法与强NPC 207
§5.4 PSPACE完全类 212
§5.5 相对化计算的概念 214
§5.6 ＃P完全性简述 216
参考文献 221