判定树理论导引

　　本书介绍计算复杂性理论的一个重要部分：判定权理论。全部内容围绕该理论中的一个重要且未解决的问题：Karp猜想。全书分九讲。前四讲介绍判定权的一般理论及Karp猜想的提出背景。五至八讲介绍研究Karp猜想的方法及已存在的成果。最后一讲介绍随机判定树以及其中的Yar：Karp猜想。作者试图通过对这一具体问题的详尽剖析，向读者展示计算复杂性理论的思想方法和意义，并将读者引入研究的前沿。本书是为数学以及理论计算机科学专业的研究生和高年级的大学生所写的通俗读物，对从事这方面工作的教师与科技工作者也有参考价值。

　　堵丁柱，黑龙江齐齐哈尔人，1948年5月生。1977年考入齐齐哈尔经工学院，1978年后随导师越民义分入应用数学所。1982年获硕士学位并赴美攻读博士。1985年于加里福尼亚大学圣巴巴拉分校获数学博士。先后工作于伯克利数学科学研究所、麻省理工学院以及普林斯顿大学。现为中国科学院应用数学所研究员，同时为美国明尼苏达大学计算机科学系正教授。自1980年从事应用数学研究以来，在国内外发表论文百余篇，并著有《可行方向方法的收剑理论》和《组合群试的理论与应用》（与黄光明合著）。现任《组合优化杂志》（英文）主编和《组合优化从书》（英文）主编。

第一讲　布尔函数与判定树
1.1　布尔函数
1.2　图与图性质
1.3　判定树
练习题
第二讲　下界与上界
2.1　隐子与子句
2.2　界
2.3　弱对称函数
练习题
第三讲　诡函数
3.1　代数判别法
3.2　弱对称诡函数
3.3　一个反例
练习题
第四讲　图性质
4.1　几个例子
4.2　Karp猜想
4.3　团与染色
练习题
第五讲　拓扑方法
5.1　单纯复形与欧拉示性数
5.2　可塌性
5.3　拓扑判别法
练习题
第六讲 不动点的妙用
6.1　不动点定理
6.2　单纯映象
6.3　二分图的性质
练习题
第七讲　置换群的应用
7.1　自同构群的不动点
7.2　Wreath积
7.3　单调图性质
练习题
第八讲　六阶图
8.1　验证Karp猜想
8.2　对有向图的注记
8.3　启迪与思考
练习题
第九讲　随机判定树
9.1　定义
9.2　下界
9.3　Yar-Karp猜想
练习题
后记
参考文献