可计算性与计算复杂性
周长林 李占山 编
吉林大学计算机科学与技术学院
目 录
第一部分 预备知识
第一章 导 引……………………………………………………………….1
1.1 集合的概念与相关运算………………………………………..2
1.2 关 系…………………………………………………………..3
1.2.1 关系的基本概念及其性质………………………………...3
1.2.2 等价关系…………………………………………………...7
1.2.3 部分序关系………………………………………………...7
1.3映 射…………………………………………………………..8
1.4定义、定理及其基本的证明技术……………………………..9
1.5字符串与语言…………………………………………………..10
第二部分可计算性理论
第二章 可计算函数…………………………………………………………11
2.1 程序设计语言................................................................................11
2.2 无条件转移和赋值的消去............................................................15
2.3 可计算函数....................................................................................16
3.4 习题与问题....................................................................................19
第三章 递归函数............................................................................................20
3.1 复合递归与取极小算子..............................................................20
3.2 原始递归函数..............................................................................22
3.3 原始递归谓词和原始递归集合..................................................25
3.4 受囿取极小值..............................................................................29
3.5 部分递归函数递归函数及其可计算性......................................35
3.6 习题与问题..................................................................................39
第四章 Post-Turing 程序和 Turing 机...........................................................41
4.1Post-Turing 程序...........................................................................41
4.2 可计算性与 P-T 可计算性..........................................................44
4.3 广义 Post-Turing 机.................................................................50
4.4Turing 机.......................................................................................54
4.5Post-Turing 程序的数字编码.......................................................60
4.6 一通用程序.................................................................................63
4.7 迭代定理.....................................................................................69
4.8 习题与问题.................................................................................71
第五章 半可计算性.......................................................................................72
5.1 半可计算谓词和半可计算集合.................................................72
5.2 半可计算的一些封闭性.............................................................77
5.3 半可计算与可计算性.................................................................83
5.4 习题与问题.................................................................................89
第六章 半图厄系统.......................................................................................90
6.1 半图厄系统.................................................................................90
6.2 用半图厄系统模拟图灵机...........................................................91
6.3 半图厄系统和半可计算集合.......................................................94
6.4 判定问题.......................................................................................96
6.5 习题与问题...................................................................................99
第七章 图灵机.................................................................................................100
7.1 引言...............................................................................................100
7.2 图灵机模型...................................................................................101
7.3 图灵机的变形...............................................................................104
7.3.1 双向无限带........................................................................104
7.3.2 多带图灵机........................................................................106
7.3.3 非确定图灵机....................................................................108
7.3.4 多维图灵机........................................................................109
7.3.5 多头图灵机........................................................................110
7.3.6 离线图灵机........................................................................111
7.4 习题...............................................................................................111
第三部分 计算复杂性
第八章 计算复杂性理论................................................................................113
8.1 复杂性定义..................................................................................113
8.1.1 空间复杂度.......................................................................113
8.1.2 时间复杂度.......................................................................113
8.1.3 关于时间和空间复杂度函数的特殊假定.......................114
8.1.4 非确定时间和空间复杂度...............................................114
8.1.5 复杂性类...........................................................................116
8.2 线性加速、带压缩和带数目的减少.....................................116
8.2.1 带压缩...............................................................................116
8.2.2 对于空间复杂性类的带数目的减少...............................117
8.2.3 线性加速...........................................................................117
8.2.4 对于时间复杂性类的带数目的减少...............................119
8.3 谱系定理...................................................................................123
8.3.1 空间谱系...........................................................................124
8.3.2 时间谱系...........................................................................127
8.4 复杂性量度间的关系................................................................128
8.5 转换引理和非确定谱系...........................................................131
8.5.1 转换引理..........................................................................131
8.5.2 一个非确定空间谱系.......................................................133
8.6 一般复杂性量度的性质：间隙定理、加速定理和并定理..134
8.6.1 加速定理............................................................................136
8.6.2 并定理................................................................................138
8.7 公理化复杂性理论....................................................................141
8.7.1Blum 公理...........................................................................142
8.7.2 复杂性量度间的递归关系................................................143
8.8习题与问题....................................................................................144
第九章 NP 完全问题简介................................................................................145
9.1 P 类和 NP 类..................................................................................145
9.1.1 可在多项式时间内解答的问题............................................145
9.1.2 非确定型多项式时间............................................................145
9.1.3 NP 完全问题..........................................................................146
9.2 多项式时间和空间.........................................................................147
9.3 某些 NP 完全问题.........................................................................150
9.3.1 可满足性问题........................................................................150
9.3.2 可满足性问题是 NP 完全的.................................................151
9.3.3 NP－完全的受限可满足性问题...........................................153
9.3.4 其他 NP 完全问题.................................................................156
第一部分 预备知识
第一章 导引
本书主要介绍可计算性与计算复杂性理论涉及到的最基本知识以及学习本书需要的入
门知识，集中在计算理论的可计算性与计算复杂性。下述问题把它们联系在一起。
计算机的基本能力和限制是什么？
这个问题要回溯到 20 世纪 30 年代，那时数理逻辑学家们首先开始探究计算的含义。自
那时起以来，技术进步极大地增强了我们的计算能力，并且把这个问题从理论王国带进现实
世界。在可计算性与计算复杂性中的每一个领域内，对这个问题作了不同的解释，并且答案
随着解释的不同而各不相同。在此，我们用相反的顺序介绍，因为从后面开始介绍能够更好
地理解本书为什么这样安排顺序。
计算复杂性理论
计算的问题是各种各样的，有的容易，有的困难。例如，排序是一个容易的问题，比
如说需要按升序排列一张数表，即使一台小型计算机都相当快地处理 100 万个数。与时间表
问题比较一下，比如说要制定一所大学的课程表，课程表必须满足某些合理的限制，如不能
有两个班在同一时间使用同一教室。时间表问题看来比排序问题困难得多。如果有 1000 个
班，即使是使用一台超级计算机，制定一份最好的课程表也可能需要若干世纪。是什么使某
些问题很难计算，又使另一些问题容易计算？这是复杂性理论的核心问题。值得注意的是，
虽然在过去的二十多年里对它进行了深入细致的研究，但是我们仍然不知道它的答案。以后
我们将探究这个迷人的问题和它的一些分支。迄今为止，复杂性理论的一个重要成果是，发
现了一个按照计算难度给问题分类的完美体系。它类似按照化学性质给元素分类的周期表。
运用这个体系，我们能够提出一种方法给出某些问题是难计算的证据，尽管还不能证明它们
是难计算的。当你面对一个看来很难计算的问题时，有几种选择。首先，搞清楚问题困难的
原因，你可能会做某些变动，使问题变的容易解决。其次，你可能会求出问题的不那么完美
的的解。在某些情况下，寻找问题的近似解相对容易一些。第三，有些问题仅仅在最坏的情
况下是困难的，而在绝大多数的时候是容易的。就应用而言，一个偶尔运行得很慢、而通常
运行得很快的过程是能够令人满意的。最后，你可以考虑其他类型的计算，如随机计算，它
能够加速某些工作。受到复杂性理论直接影响的一个应用领域是密码技术，这是一个古老的
研究领域。在绝大多数的情况下，容易计算的问题比难计算的问题更可取，因为求解容易的
1
- 1
- 2
前往页