可计算性与计算复杂性导引

第一章程序设计语言少和可计算函数
1.1预备知识
1.2Church-Turing论题
1.3程序设计语言少
1.4可计算函数
1.5宏指令
习题
第二章原始递归函数
2.1原始递归函数
2.2原始递归谓词
2.3迭代运算.有界量词和极小化
2.4配对函数和Godel数
2.5原始递归运算
2.6Ackermann函数
2.7字函数的可计算性
习题
第三章通用程序
3.1程序的代码
3.2停机问题
3.3通用程序
3.4递归可枚举集
习题
第四章Turing机
4.1Turing机的基本模型
4.2Turing机的各种形式
4.3Turing机与可计算性
4.4Turing机接受的语言
4.5非确定型Turing机
习题
第五章过程与文法
5.1半Thue过程
5.2用半Thue过程模拟Turing机
5.3文法
5.4再论递归可枚举集
5.5部分递归函数
5.6再论Church-Turing论题
习题
第六章不可判定的问题
6.1判定问题
6.2Turing机的停机问题
6.3字问题和Post对应问题
6.4有关文法的不可判定问题
6.5一阶逻辑中的判定问题
习题
第七章正则语言
7.1Chomsky谱系
7.2有穷自动机
7.3有穷自动机与正则文法的等价性
7.4正则表达式
7.5非正则语言
习题
第八章上下文无关语言
8.1上下文无关文法
8.2Chomsky范式
8.3Bar-Hillel泵引理
8.4下推自动机
8.5上下文无关文法与下推自动机的等价性
8.6确定型下推自动机
8.7上-F文有关文法
习题
第九章时间复杂性与空间复杂性
9.1Turing机的运行时间和工作空间
9.2计算复杂性类
9.3复杂性类的真包含关系
习题
第十章NP完全性
10.1P与NP
10.2多项式时间变换和NP完全性
10.3Cook定理
10.4若千NP完全问题
10.5coNP
习题
第十一章NP类的外面
11.1PSPACE完全问题
11.2一个难解问题
习题
第十二章P类的里面
12.1若干例子
12.2对数空间变换
12.3NL类
12.4P完全问题
习题
第十三章随机算法与随机复杂性类
13.1随机算法
13.2随机复杂性类
习题
附录
附录A记号
附录B中英文名词索引
参考文献