判定树理论导引
作者：堵丁柱
ISBN：10位［7535526004］13位［9787535526007］
出版社：湖南教育出版社
出版日期：1998年
定价：￥6.20元
内容提要本书介绍计算复杂性理论的一个重要部分----判定权理论。全部内容围绕该理论中的一个重要且未解决的问题----Karp猜想。
全书分九讲。前四讲介绍判定权的一般理论及Karp猜想的提出背景。五至八讲介绍研究Karp猜想的方法及已存在的成果。最后一讲介绍随机判定树以及其中的Yar----Karp猜想。作者试图通过对这一具体问题的详尽剖析，向读者展示计算复杂性理论的思想方法和意义，并将读者引入研究的前沿。本书是为数学以及理论计算机科学专业的研究生和高年级的大学生所写的通俗读物，对从事这方面工作的教师与科技工作者也有参考价值。
编辑推荐本书介绍计算复杂性理论的一个重要部分----判定权理论。全部内容围绕该理论中的一个重要且未解决的问题----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.2Karp猜想
4.3团与染色
练习题
第五讲拓扑方法
5.1单纯复形与欧拉示性数
5.2可塌性
5.3拓扑判别法
练习题
第六讲不动点的妙用
6.1不动点定理
6.2单纯映象
6.3二分图的性质
练习题
第七讲置换群的应用
7.1自同构群的不动点
7.2Wreath积
7.3单调图性质
练习题
第八讲六阶图
8.1验证Karp猜想
8.2对有向图的注记
8.3启迪与思考
练习题
第九讲随机判定树
9.1定义
9.2下界
9.3Yar-Karp猜想
练习题
后记
参考文献