基本信息
- 原书名：Computational Complexity
编辑推荐
计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域，是理论计算机科学研究的重要内容。本书重点介绍复杂性的计算、问题和逻辑。本书包含五部分：第一部分介绍算法，包括问题与算法、图灵机、不可判定性；第二部分介绍逻辑学，包括布尔逻辑、一阶逻辑和逻辑中的不可判定性；第三部分介绍P和NP，包括复杂性类之间的关系、归约和完备性、NP完全问题、coNP和函数问题、随机计算、密码学、可近似性等；第四部分介绍P内部的计算复杂性，包括并行计算、对数空间；第五部分介绍NP之外的计算复杂性类，包括多项式谱系、计数的计算、多项式空间等。
本书不需要数学预备知识。每章最后一节包括相关的注解、参考文献和问题，很多问题涉及更深的结论和研究。本书适合于作为高年级本科生和低年级研究生计算复杂性理论课程的教材。
内容简介
书籍
计算机书籍
计算复杂性理论的研究是计算机科学最重要的研究领域之一，而Chistos H.Papadimitriou是该领域量著名的专家之一。
计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域，是理论计算机科学研究的重要内容。复杂性是计算（复杂性类)和应用(问题)之间复杂而核心的部分。
本书是一本全面阐述计算复杂理论及其近年来进展的教科书，内容颇为深奥，重点介绍复杂性的计算、问题和逻辑。本书主要内容包含算法图灵机、可计算性等有关计算复杂性理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外(如多项式空间等)复杂性类的介绍。每章最后一节包括相关的参考文献、注解、练习和问题，很多问题涉及更深的结论和研究。
计算机书籍
计算复杂性理论的研究是计算机科学最重要的研究领域之一，而Chistos H.Papadimitriou是该领域量著名的专家之一。
计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域，是理论计算机科学研究的重要内容。复杂性是计算（复杂性类)和应用(问题)之间复杂而核心的部分。
本书是一本全面阐述计算复杂理论及其近年来进展的教科书，内容颇为深奥，重点介绍复杂性的计算、问题和逻辑。本书主要内容包含算法图灵机、可计算性等有关计算复杂性理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外(如多项式空间等)复杂性类的介绍。每章最后一节包括相关的参考文献、注解、练习和问题，很多问题涉及更深的结论和研究。
作译者
克里斯特斯H.帕帕季米特里乌（Chistos H.Papadimitriou）是当今计算机科学界最活跃和有影响力的科学家之一。Papadimitriou拥有普林斯顿大学博士学位。现为加州大学伯克利分校计算机科学系教授。他曾在哈佛大学、麻省理工学院、雅典工艺大学、斯坦福大学、加州大学圣地亚哥分校任教。他是美国科学院院士、美国工程院院士和美国人文科学院院士。他于2002年获得高德纳奖，2012年获得哥德尔奖。他的主要研究领域是算法和复杂性，以及它们在优化、数据库、人工智能、经济和互联网等方面的应用，曾撰写此领域教科书5本，发表论文数篇。
目录
出版者的话
译者序
前言
第一部分算法
第1章问题与算法
1.1图的可达性问题
1.2最大流问题
1.3旅行商问题
1.4注解、参考文献和问题
第2章图灵机
2.1图灵机概述
2.2视为算法的图灵机
2.3多带图灵机
2.4线性加速
2.5空间界
2.6随机存取机
2.7非确定性机
2.8注解、参考文献和问题
第3章不可判定性
3.1通用图灵机
译者序
前言
第一部分算法
第1章问题与算法
1.1图的可达性问题
1.2最大流问题
1.3旅行商问题
1.4注解、参考文献和问题
第2章图灵机
2.1图灵机概述
2.2视为算法的图灵机
2.3多带图灵机
2.4线性加速
2.5空间界
2.6随机存取机
2.7非确定性机
2.8注解、参考文献和问题
第3章不可判定性
3.1通用图灵机
译者序
经过多年努力，本书终于翻译完成了。作者Papadimitriou为著名的理论计算机科学家，对计算复杂性有着比较全面而深刻的见解，因此本书内容也颇为深奥。在长期的翻译和学习中，我们体会到该书对于从事计算理论研究的相关人员来说确实是一本优秀的基础参考书，认真学习本书的读者必能受益匪浅。我们在翻译过程中也是收获良多，补习了不少原先忽略的知识。本书总结了截至1994年计算理论领域中的最新研究成果，其中有概率可验证证明（PCP)、零知识证明（Zeroknowledge proof system)等当时极其前沿并且对日后的学科发展起到关键性作用的内容，本书对这些专门知识给予了简洁的阐释。
读者通过本书的阅读和习题，可以对20世纪90年代中期的计算理论发展脉络有一个比较清楚的了解，从而打下良好的研究基础。但是，由于目前已经是21世纪10年代了，而计算理论在最近20多年里又有了蓬勃的发展，所以译者建议想进一步了解计算理论的读者可以补充阅读以下书籍：
Sanjeev Arora and Boaz Barak Computational Complexity: A Modern Approach Cambridge University Press, 2009
Oded GoldreichComputational Complexity: A Conceptual PerspectiveCambridge University Press, 2008
Mikhail JAtallah and Marina Blanton Algorithms and Theory of Computation Handbook CRC Press, 2009
对于NP难优化问题的近似算法和难近似性，译者推荐补充阅读以下两本书：
Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto MarchettiSpaccamela and MarcoProtasi.Complexity and Approximation: Combinatorial Optimization Problems and Their Approximabiltiy Properties. Springer, 2003
Vijay VVazirani.Approximation Algorithm. Springer, 2001
近30年来，量子计算、量子复杂性和算法得到长足的发展，并且具有远大的潜力，译者推荐如下两本书和一篇综述：
Michael ANielson and Isaac LChuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000
Jozef Gruska. Quantum Computing, McGrawHill, New York, 1999
Lance Fortnow. One Complexity Theorists View of Quantum Computing. Theoretical Computer Science, Vol 292, pp597610, 2003
在参数复杂性和算法机制设计方面，译者推荐两篇代表性综述：
Rod Downey. Basic Parametric Complexity II: Intractability. Victoria University WellingtonIsaac Newton Institute, Cambridge, LATA, March 2012
Noam Nisan and Amir Ronen. Algorithmic mechanism design. Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, pp129140, 1999
最后，作为补充阅读，译者还推荐以下两本中文书籍：
堵丁柱，葛可一,王洁计算复杂性导论高等教育出版社，2002
堵丁柱，葛可一,胡晓东近似算法的设计与分析高等教育出版社，2011
全书译者分工如下：前言和第1、2、3章由倪盛宇和朱洪翻译，第4、5、6章由彭超翻译，第7、8、11、12、14、20章由朱洪翻译，第9章由王怡慧翻译，第10、13章由陈崇琛翻译，第15、16、17、18章由卜天明翻译，第19章由卜天明、陈崇琛、王怡慧、朱洪各译一节。由于译者较多，译稿难免有不统一和不准确之处，欢迎读者随时通过电子邮件hzhu@fudan.edu.cn提出宝贵意见。
译者
读者通过本书的阅读和习题，可以对20世纪90年代中期的计算理论发展脉络有一个比较清楚的了解，从而打下良好的研究基础。但是，由于目前已经是21世纪10年代了，而计算理论在最近20多年里又有了蓬勃的发展，所以译者建议想进一步了解计算理论的读者可以补充阅读以下书籍：
Sanjeev Arora and Boaz Barak Computational Complexity: A Modern Approach Cambridge University Press, 2009
Oded GoldreichComputational Complexity: A Conceptual PerspectiveCambridge University Press, 2008
Mikhail JAtallah and Marina Blanton Algorithms and Theory of Computation Handbook CRC Press, 2009
对于NP难优化问题的近似算法和难近似性，译者推荐补充阅读以下两本书：
Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto MarchettiSpaccamela and MarcoProtasi.Complexity and Approximation: Combinatorial Optimization Problems and Their Approximabiltiy Properties. Springer, 2003
Vijay VVazirani.Approximation Algorithm. Springer, 2001
近30年来，量子计算、量子复杂性和算法得到长足的发展，并且具有远大的潜力，译者推荐如下两本书和一篇综述：
Michael ANielson and Isaac LChuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000
Jozef Gruska. Quantum Computing, McGrawHill, New York, 1999
Lance Fortnow. One Complexity Theorists View of Quantum Computing. Theoretical Computer Science, Vol 292, pp597610, 2003
在参数复杂性和算法机制设计方面，译者推荐两篇代表性综述：
Rod Downey. Basic Parametric Complexity II: Intractability. Victoria University WellingtonIsaac Newton Institute, Cambridge, LATA, March 2012
Noam Nisan and Amir Ronen. Algorithmic mechanism design. Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, pp129140, 1999
最后，作为补充阅读，译者还推荐以下两本中文书籍：
堵丁柱，葛可一,王洁计算复杂性导论高等教育出版社，2002
堵丁柱，葛可一,胡晓东近似算法的设计与分析高等教育出版社，2011
全书译者分工如下：前言和第1、2、3章由倪盛宇和朱洪翻译，第4、5、6章由彭超翻译，第7、8、11、12、14、20章由朱洪翻译，第9章由王怡慧翻译，第10、13章由陈崇琛翻译，第15、16、17、18章由卜天明翻译，第19章由卜天明、陈崇琛、王怡慧、朱洪各译一节。由于译者较多，译稿难免有不统一和不准确之处，欢迎读者随时通过电子邮件hzhu@fudan.edu.cn提出宝贵意见。
译者
前言
我仅仅希望简单叙述
请赋予我这一特权
因为我们已经被灌输了带有这么多音乐的歌声
音乐正在沉沦
而我们的艺术变得如此矫饰
以至于装饰品已经腐蚀了她的容颜
是时候说一些简单的语言了
因为明天我们的心灵将起帆远航
——Giorgos Seferis
本书适合作为低年级研究生或者高年级本科生学习计算复杂性理论的教材。计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域。这个领域以前几乎不存在，而现在却迅速扩展，并构成了理论计算机科学研究活动的主要内容。现在没有一本书可以全面介绍复杂性——当然也包括这本书在内。本书只是包含了我认为可以清楚和相对简单地表示的结果以及在我看来是复杂性领域的中心内容。
我认为复杂性是计算(复杂性类)和应用(问题)之间复杂而核心的部分。开篇就向读者灌输这一观点有点为时过早，不过我还是要冒险一试，而且这也将是全书20章中反复强调的观点。完全性的结论明显是这一进展的中心环节。逻辑也是如此，它能很好地表达和抓住计算这一概念，是非常重要的应用。因此计算、问题和逻辑是贯穿本书的三大主脉络。
内容
快速浏览目录，第1章介绍问题和算法——因为当复杂性与简单性比较时，复杂性最好理解。第2章讨论图灵机，同时明确我们的方式将不依赖于机器。第3章介绍非确定性（它不仅是复杂性的最高形式，而且还具有重大的方法学影响）。
接着讨论逻辑。这一部分最可能会被复杂性理论同行视为另类。但是它对于我看待复杂性的观点非常重要，对于计算机科学非常基本，又很少作为走向计算机科学家的成功之路看待，所以我感到我必须做一次尝试。第4章介绍布尔逻辑（包括Horn子句的算法属性，以及布尔电路和香农定理）。第5章介绍一阶逻辑及其模型论和证明论，还包括完全性定理，以及足够的二阶逻辑以引出随后的NP的Fagin特征——非常有用但是往往被忽视，其意义相当于Cook定理。第6章是对Gdel不完全性定理的独立证明，该证明是逻辑表达计算早期的重要例子。
然后重点介绍复杂性。第7章介绍已知的复杂性类之间的关系——包括Savitch和 ImmermanSzelepscényi关于空间复杂性的定理。第8章介绍归约和完全性概念，紧接着，作为例子，介绍Cook定理和电路值问题的P完全性，同时比较用逻辑表示P和NP的特征。第9章包含很多NP完全的结果，同时介绍各种证明方法。第10章讨论coNP和函数问题。第11章介绍随机算法、与之对应的复杂性类以及用现实随机源的实现方法。电路和它们与复杂性、随机化的关系也在此介绍。第12章很简短，粗略介绍密码学和协议。第13章讨论近似算法，以及最近通过
概率可验证性证明得出的一些不可行性方面的结果。另一方面，第14章讨论P=?NP问题的结构性方面，比如，中间度、同构、稠密性和谕示。它还包含了Razborov关于单调电路的下界证明。
第15章进一步关注P、并行算法及其复杂性，第16章重点讨论对数空间，包括无向图路径的随机游走算法。最后，除了NP以外，第17章给出多项式谱系（包括优化问题的Krentel特征）；第18章讲述计数问题和关于积和式的Valiant定理；第19章介绍多项式空间的许多方面（最有趣的是关于交互式协议的Shamir定理）；本书最后对难解性领域做了简短展望。
本书并没有特别的数学基础要求——除了要有一定程度的“数学成熟度”，而数学成熟度这个名词，一般不在序言中给予定义。所有的定理都从基本原理给予证明（除了第13章关于近似性引用了两个定理外），同时更多的相关结果在每章最后一节中说明。证明和构造经常会比文献里讲述的简单得多。实际上，本书包含了多个与复杂性相关的主题或专题简介：基础数论（用来证明Pratt定理），SolovayStrassen素数测定和RSA密码协议（第10、11、12章）；基础概率（第11章和其他章节）；组合数学和概率方法（第10、13、14章）；递归理论（第3、14章）；逻辑（第4、5、6章）。由于复杂性问题总是和相对应的算法概念的全面发展联系在一起（第1章的有效算法，第11章的随机算法，第13章的近似算法和第15章的并行算法），所以本书也可以作为算法引论——虽然仅仅粗略分析，但是可以应用在各种情况。
注解和问题
每章的最后一节包含了相关的文献、注解、练习和问题。很多问题涉及更深的结论和课题。就我看来，这是一章中最重要的部分（经常也是最长的），读者应该将它作为本书的一部分来阅读。它经常给出历史观点，并把该章放到了更广泛的领域中。所有这些题目都是可做的，至少在提示下去图书馆查阅答案（我已经发现这样做至少对我的学生来说，不亚于另一次智商测验）。对这些题目没有标记难易，不过对于真正的难题还是给出了警示标记。
请赋予我这一特权
因为我们已经被灌输了带有这么多音乐的歌声
音乐正在沉沦
而我们的艺术变得如此矫饰
以至于装饰品已经腐蚀了她的容颜
是时候说一些简单的语言了
因为明天我们的心灵将起帆远航
——Giorgos Seferis
本书适合作为低年级研究生或者高年级本科生学习计算复杂性理论的教材。计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域。这个领域以前几乎不存在，而现在却迅速扩展，并构成了理论计算机科学研究活动的主要内容。现在没有一本书可以全面介绍复杂性——当然也包括这本书在内。本书只是包含了我认为可以清楚和相对简单地表示的结果以及在我看来是复杂性领域的中心内容。
我认为复杂性是计算(复杂性类)和应用(问题)之间复杂而核心的部分。开篇就向读者灌输这一观点有点为时过早，不过我还是要冒险一试，而且这也将是全书20章中反复强调的观点。完全性的结论明显是这一进展的中心环节。逻辑也是如此，它能很好地表达和抓住计算这一概念，是非常重要的应用。因此计算、问题和逻辑是贯穿本书的三大主脉络。
内容
快速浏览目录，第1章介绍问题和算法——因为当复杂性与简单性比较时，复杂性最好理解。第2章讨论图灵机，同时明确我们的方式将不依赖于机器。第3章介绍非确定性（它不仅是复杂性的最高形式，而且还具有重大的方法学影响）。
接着讨论逻辑。这一部分最可能会被复杂性理论同行视为另类。但是它对于我看待复杂性的观点非常重要，对于计算机科学非常基本，又很少作为走向计算机科学家的成功之路看待，所以我感到我必须做一次尝试。第4章介绍布尔逻辑（包括Horn子句的算法属性，以及布尔电路和香农定理）。第5章介绍一阶逻辑及其模型论和证明论，还包括完全性定理，以及足够的二阶逻辑以引出随后的NP的Fagin特征——非常有用但是往往被忽视，其意义相当于Cook定理。第6章是对Gdel不完全性定理的独立证明，该证明是逻辑表达计算早期的重要例子。
然后重点介绍复杂性。第7章介绍已知的复杂性类之间的关系——包括Savitch和 ImmermanSzelepscényi关于空间复杂性的定理。第8章介绍归约和完全性概念，紧接着，作为例子，介绍Cook定理和电路值问题的P完全性，同时比较用逻辑表示P和NP的特征。第9章包含很多NP完全的结果，同时介绍各种证明方法。第10章讨论coNP和函数问题。第11章介绍随机算法、与之对应的复杂性类以及用现实随机源的实现方法。电路和它们与复杂性、随机化的关系也在此介绍。第12章很简短，粗略介绍密码学和协议。第13章讨论近似算法，以及最近通过
概率可验证性证明得出的一些不可行性方面的结果。另一方面，第14章讨论P=?NP问题的结构性方面，比如，中间度、同构、稠密性和谕示。它还包含了Razborov关于单调电路的下界证明。
第15章进一步关注P、并行算法及其复杂性，第16章重点讨论对数空间，包括无向图路径的随机游走算法。最后，除了NP以外，第17章给出多项式谱系（包括优化问题的Krentel特征）；第18章讲述计数问题和关于积和式的Valiant定理；第19章介绍多项式空间的许多方面（最有趣的是关于交互式协议的Shamir定理）；本书最后对难解性领域做了简短展望。
本书并没有特别的数学基础要求——除了要有一定程度的“数学成熟度”，而数学成熟度这个名词，一般不在序言中给予定义。所有的定理都从基本原理给予证明（除了第13章关于近似性引用了两个定理外），同时更多的相关结果在每章最后一节中说明。证明和构造经常会比文献里讲述的简单得多。实际上，本书包含了多个与复杂性相关的主题或专题简介：基础数论（用来证明Pratt定理），SolovayStrassen素数测定和RSA密码协议（第10、11、12章）；基础概率（第11章和其他章节）；组合数学和概率方法（第10、13、14章）；递归理论（第3、14章）；逻辑（第4、5、6章）。由于复杂性问题总是和相对应的算法概念的全面发展联系在一起（第1章的有效算法，第11章的随机算法，第13章的近似算法和第15章的并行算法），所以本书也可以作为算法引论——虽然仅仅粗略分析，但是可以应用在各种情况。
注解和问题
每章的最后一节包含了相关的文献、注解、练习和问题。很多问题涉及更深的结论和课题。就我看来，这是一章中最重要的部分（经常也是最长的），读者应该将它作为本书的一部分来阅读。它经常给出历史观点，并把该章放到了更广泛的领域中。所有这些题目都是可做的，至少在提示下去图书馆查阅答案（我已经发现这样做至少对我的学生来说，不亚于另一次智商测验）。对这些题目没有标记难易，不过对于真正的难题还是给出了警示标记。
书摘
3.2停机问题
通用图灵机的存在很快并不可避免地引出不可判定问题，即没有算法的问题，非递归的语言。不可判定性从一开始就成为计算机科学文化的一部分，以至于非常容易忘记其奇怪的一面。严格来讲，一旦我们将语言等同为问题，而将图灵机等同为算法，不可判定问题的存在就显而易见了：语言的种类（不可数）多于判定语言的方法（图灵机）。然而，当它在20世纪30年代首次发现时，这样接近于我们计算能力极限问题的存在，还是造成了轰动。不可判定性在某种程度上是复杂性的最难形式，所以值得在本书前面章节提及。而且，不可判定性理论的发展是复杂性理论的重要先驱，也是方法学、类比和准则的有用来源。
我们如下定义HALTING：给定图灵机M的描述和它的输入x，M停机于x吗？作为语言形式，我们令H是定义在3.1节中通用机U字母表上的语言：H={M；x：M（x）≠／）。即语言H包含了所有编码为图灵机和输入的字符串，使得该图灵机停机于该输入。容易得到以下性质：
性质3.1 H是递归可枚举语言。
证明：我们只要设计接受H的图灵机，即如果其输入属于H，停机输出“yes”，否则永不停机。容易看到，所需要的机器就是前3.1节的通用图灵机。我们只需要做微小改动使得每次它都停机于“yes”状态。
实际上，H不仅仅是递归可枚举语言。在所有的递归可枚举语言中，HALTING有重要的属性：如果有某个算法来判定HALTING，那么我们可以构造算法来判定任意递归可枚举语言：令L为图灵机M接受的递归可枚举语言。给定输入x，我们可以简单地通过判定M；x∈H来判定是否有x∈L。可以说，所有递归可枚举语言都可以归约到H。因此HALTING是递归可枚举语言的完全问题。归约和完全性的准确概念将是研究远不止这些（这些将马上解决）复杂性情况的有用工具。典型地，完全性是问题不能满意解决的征兆。
通用图灵机的存在很快并不可避免地引出不可判定问题，即没有算法的问题，非递归的语言。不可判定性从一开始就成为计算机科学文化的一部分，以至于非常容易忘记其奇怪的一面。严格来讲，一旦我们将语言等同为问题，而将图灵机等同为算法，不可判定问题的存在就显而易见了：语言的种类（不可数）多于判定语言的方法（图灵机）。然而，当它在20世纪30年代首次发现时，这样接近于我们计算能力极限问题的存在，还是造成了轰动。不可判定性在某种程度上是复杂性的最难形式，所以值得在本书前面章节提及。而且，不可判定性理论的发展是复杂性理论的重要先驱，也是方法学、类比和准则的有用来源。
我们如下定义HALTING：给定图灵机M的描述和它的输入x，M停机于x吗？作为语言形式，我们令H是定义在3.1节中通用机U字母表上的语言：H={M；x：M（x）≠／）。即语言H包含了所有编码为图灵机和输入的字符串，使得该图灵机停机于该输入。容易得到以下性质：
性质3.1 H是递归可枚举语言。
证明：我们只要设计接受H的图灵机，即如果其输入属于H，停机输出“yes”，否则永不停机。容易看到，所需要的机器就是前3.1节的通用图灵机。我们只需要做微小改动使得每次它都停机于“yes”状态。
实际上，H不仅仅是递归可枚举语言。在所有的递归可枚举语言中，HALTING有重要的属性：如果有某个算法来判定HALTING，那么我们可以构造算法来判定任意递归可枚举语言：令L为图灵机M接受的递归可枚举语言。给定输入x，我们可以简单地通过判定M；x∈H来判定是否有x∈L。可以说，所有递归可枚举语言都可以归约到H。因此HALTING是递归可枚举语言的完全问题。归约和完全性的准确概念将是研究远不止这些（这些将马上解决）复杂性情况的有用工具。典型地，完全性是问题不能满意解决的征兆。
