计算复杂性

 

计算机复杂理论的研究是计算机科学*重要的研究领域之一，而Chistos.H.Papadimitriou是该领域*著名的专家之一。本书是一本全面阐述计算机复杂性理论及其近年来进展的教科书，主要包含算法图灵机、可计算性等有关计算复杂理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；*算法、近似算法、并行算法及其复杂性理论；以及NP之外如多项式空间等复杂性类的介绍。

目录
Computational Complexity
出版者的话
译者序
前言
第一部分算法
第1章问题与算法
11图的可达性问题
12最大流问题
13旅行商问题
14注解、参考文献和问题
第2章图灵机
21图灵机概述
22视为算法的图灵机
23多带图灵机
24线性加速
25空间界
26随机存取机
27非确定性机
28注解、参考文献和问题
第3章不可判定性
31通用图灵机
32停机问题
33更多不可判定性问题
34注解、参考文献和问题
第二部分逻辑学
第4章布尔逻辑
41布尔表达式
42可满足性与永真性
43布尔函数与电路
44注解、参考文献和问题
第5章一阶逻辑
51一阶逻辑的语法
52模型
53永真的表达式
54公理和证明
55完备性定理
56完备性定理的推论
57二阶逻辑
58注解、参考文献和问题
第6章逻辑中的不可判定性
61数论公理
62作为一个数论概念的计算
63不可判定性与不完备性
64注解、参考文献和问题
第三部分P和NP
第7章复杂性类之间的关系
71复杂性类
72谱系定理
73可达性方法
74注解、参考文献和问题
第8章归约和完备性
81归约
82完全性
83逻辑特征
84注解、参考文献和问题
第9章NP完全问题
91NP中的问题
92可满足性问题的不同版本
93图论问题
94集合和数字
95注解、参考文献和问题
第10章coNP和函数问题
101NP和coNP
102素性
103函数问题
104注解、参考文献和问题
第11章随机计算
111随机算法
112随机复杂性类
113随机源
114电路复杂性
115注解、参考文献和问题
第12章密码学
121单向函数
122协议
123注解、参考文献和问题
第13章可近似性
131近似算法
132近似和复杂性
133不可近似性
134注解、参考文献和问题
第14章关于P和NP
141NP的地图
142同构和稠密性
143谕示
144单调电路
145注解、参考文献和问题
第四部分P内部的计算复杂性类
第15章并行计算
151并行算法
152计算的并行模型
153NC类
154RNC算法
155注解、参考文献和问题
第16章对数空间
161L=?NL问题
162交错
163无向图的可达性
164注解、参考文献和问题
第五部分NP之外的计算复杂性类
第17章多项式谱系
171优化问题
172多项式谱系
173注解、参考文献和问题
第18章有关计数的计算
181积和式
182P类
183注解、参考文献和问题
第19章多项式空间
191交错和博弈
192对抗自然的博弈和交互协议
193更多的PSPACE完全问题
194注解、参考文献和问题
第20章未来的展望
201指数时间复杂性类
202注解、参考文献和问题
索引

 

前言Computational Complexity我仅仅希望简单叙述请赋予我这一特权因为我们已经被灌输了带有这么多音乐的歌声音乐正在沉沦而我们的艺术变得如此矫饰以至于装饰品已经腐蚀了她的容颜是时候说一些简单的语言了因为明天我们的心灵将起帆远航——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章的并行算法），所以本书也可以作为算法引论——虽然仅仅粗略分析，但是可以应用在各种情况。

    注解和问题每章的最后一节包含了相关的文献、注解、练习和问题。很多问题涉及更深的结论和课题。就我看来，这是一章中最重要的部分（经常也是最长的），读者应该将它作为本书的一部分来阅读。它经常给出历史观点，并把该章放到了更广泛的领域中。所有这些题目都是可做的，至少在提示下去图书馆查阅答案（我已经发现这样做至少对我的学生来说，不亚于另一次智商测验）。对这些题目没有标记难易，不过对于真正的难题还是给出了警示标记。

    教学本书的重点显然是复杂性，所以我们将它设计成（以及用作）计算机科学家关于计算理论的入门级读物。我和我的同事在过去的三年中用它作为加州大学圣地亚哥分校硕士研究生第一年为期10周的教材。前两周学习前4章，这些内容对于本科生来说，一般都已熟悉。逻辑学安排在紧接着的3周中，经常省略完全性证明。剩下的5周学习第7章，作为NP完全性的严格训练（不包括在该校的算法课内），选择第11～14章中的一两节。一学期的课程可以涵盖以上4章。如果你想跳过逻辑学部分，可以加上第15章（然而，我相信这样做会错过本书相当好的一部分内容）。

    本书至少还可以用于两门课程：前9章的主题对于计算机科学家很关键，所以它可以自豪地替代高年级本科生初级理论课程中的自动机和形式语言（特别是，因为现在的编译课程都已独立出来）。我也两次使用后面的11章作为理论方向的第二学期课程，其目标是带领有兴趣的研究生进入复杂性的研究课题——或者至少帮助他们成为计算机理论会议上见多识广的听众。

    感谢我关于复杂性的想法是我的老师、学生和同事长期鼓舞和启迪的结果。我非常感谢所有这些人：Ken Steiglitz、Jeff Ullman、Dick Karp、Harry Lewis、John Tsitsiklis、Don Knuth、Steve Vavasis、Jack Edmonds、Albert Meyer、Gary Miller、Patrick Dymond、Paris Kanellakis、David Johnson、Elias Koutsoupias（他也在图表、最后检查和索引上给予我很多帮助）、Umesh Vazirani、Ken Arrow、Russell Impagliazzo、Sam Buss、Milena Mihail、Vijay Vazirani、Paul Spirakis、Pierluigi Crescenzi、Noga Alon、Stathis Zachos、Heather Woll、Phokion Kolaitis、Neil Immerman、Pete Veinott、Joan Feigenbaum、Lefteris Kirousis、Deng Xiaotie、Foto Afrati、Richard Anderson，最主要的是Mihalis Yannakakis和Mike Sipser。他们阅读了本书的草稿并提出了建设性意见、想法和建议——否则就会让我为他们的沉默而紧张。在所有对我的课件提出评论的学生中，我记得名字的只有David Morgenthaller、Goran Gogic、Markus Jacobsson和George Xylomenos（但我记住了其余人的笑容）。最后，感谢Richard Beigel、Matt Wong、Wenhong Zhu和他们在耶鲁的复杂性班，他们找出了本书初稿中的许多错误。自然，我对剩下的错误负责——尽管我认为我的朋友当初可以找出更多的错误。

    我非常感激Martha
Sideri的鼓励和支持，以及她的注解、看法和封面设计。

    我在加州大学圣地亚哥分校工作时完成本书，但这期间我也访问了AT&T公司的贝尔实验室、Bonn大学、Saarbrücken的MaxPlanck研究所、Patras大学和那里的计算机学院以及巴黎 Sud 大学。我对于算法和复杂性的研究受到美国国家科学基金、Esprit项目AlCOM以及加州大学圣地亚哥分校信息和计算机科学主席Irwin Mark和Joan Klein Jacobs的资助。

    与AddisonWesley的Tom Stone及其同事一起完成本书出版是愉快的。最后，我使用了Don Knuth的TeX排版，我的宏是从Jeff Ullman很多年前给我的那些中演变而来的。

    Christos H.Papadimitriou