计算复杂性导论

图书标准信息

• 作者 堵丁柱、葛可一、王杰 著
• 出版社 高等教育出版社
• 出版时间 2002-08
• 版次 1
• ISBN 9787040113075
• 定价 53.00元
• 装帧 精装
• 开本 16开
• 纸张 胶版纸
• 页数 378页
• 字数 370千字
• 正文语种 简体中文
• 丛书 当代科学前沿论丛

【内容简介】

　　《计算复杂性导论（精）》可用作计算机专业、计算数学专业的计算机理论课程的教材，也是有关研究人员不可或缺的参考书。计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论。《计算复杂性导论（精）》对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论，如计算模型NP-完全性，以及较深入的课题，如线路复杂性、概率复杂性和交互证明系统等。此外，《计算复杂性导论（精）》还包括了复杂性理论近年来两个较重大的突破，即概率可验证明及其在近似算法上的应用和平均NP-完全理论。《计算复杂性导论（精）》中所有结果均有严格的数学证明，在每章后配有相关练习题。

【作者简介】

　　堵丁柱，1948年生。中国科学院应用数学所运筹学硕士（1981）。美国加里福利亚大学圣巴巴拉分校数学博士（1985）。美国伯克利数学科学研究所博士后（1985.1986）。美国麻省理工学院助理教授（1986－1987）。美国普林斯顿大学访问学者（1990－1991）。现任美国明尼苏达大学计算机科学系教授，中国科学院应用数学所研究员。Journal0fCombinatorialOptimization主编，BookSeriesofCombinatorialOptimization和BookSeriesofNetworksTheoryandApplications主编。主要研究方向为组合优化，计算复杂性，算法分析与设计，计算机和通讯网络。发表论文130篇，著书7本。1993年获中国科学院自然科学一等奖。1995年获中国自然科学二等奖。1998年获美国运筹和管理学会CSTC奖（计算机与运筹学边缘科学奖）。
　　葛可一，1950年生。台湾新竹清华大学数学学士（1972）。美国俄亥俄州立大学数学硕士（1974），计算机科学博士（1979）。现任美国纽约州立大学石溪分校计算机科学系教授.SIAMJournalonComputing与JournalofComplexity编辑。曾主持多项美国自然科学基金会研究课题。主要研究方向为计算复杂性理论，数值计算复杂性和可计算性理论。发表论文55篇，著书3本。
　　王杰，1961年生。中山大学计算机科学系计算数学专业学士（1982），软件专业硕士（1984），美国波士顿大学计算机科学博士（1990）。现任美国麻萨诸塞大学罗威尔分校计算机科学系教授，并任网络与系统安全实验室主任。主要研究方向为平均计算复杂性理论，网络与系统安全，应用算法。曾主持多项美国自然科学基金会的课题及美国英特尔（Intel）公司的课题。发表论文70篇及编书两本。1991年获美国自然科学基金会科研启动奖，2002年获英特尔公司大学项目IXA研究奖。

【目录】

前言
第一章计算模型
1.1符号行，编码和布尔函数
1.2确定型图灵机
1.3非确定型图灵机
练习题
第二章计算复杂性类
2.1时间与空间
2.2通用图灵机
2.3对角线方法
2.4模拟
练习题
第三章NP-完全问题
3.1NP
3.2Cook定理
3.3NP-完全问题的例子
3.4多项式时间图灵归约
练习题
第四章多项式时间分层和多项式空间
4.1非确定型带神喻图灵机
4.2多项式时间分层
4.3PH中的完全问题
4.4交替图灵机
4.5PSPACE-完全问题
练习题
第五章线路复杂性
5.1布尔线路
5.2单调递增函数与单调线路
5.3奇偶性函数与深度有界线路
5.4多项式规模布尔线路
练习题
第六章NP类的结构
6.1NP中的非完全问题
6.2单向函数及其在密码学中的应用
6.3NC
6.4P-完全性
6.5NP-完全问题的密度
6.6EXP-完全问题的密度
练习题
第七章概率机与复杂性类
7.1随机算法
7.2概率图灵机及其时间复杂性
7.3带有界误差的概率机
7.4BPP，NP和多项式时间分层
练习题
第八章计数复杂性
8.1计数类#P
8.2#P-完全问题
8.3■P和多项式时间分层
8.4#P和多项式时间分层
练习题
第九章交互证明系统
9.1例子与定义
9.2亚瑟默林证明系统
9.3AM分层与多项式时间分层
9.4IP与AM
9.5IP与PSPACE
练习题
第十章概率可验证明
10.1PCP的定义
10.2NEXPPOLY的PCP特征
10.2.1主要证明
10.2.2多重线性测试系统
10.2.3和检验系统
10.3NP的PCP特征
10.3.1使用O(logn)个随机数码的PCP系统
10.3.2低阶测试系统
10.3.3两个PCP系统的复合
10.3.4阅读常数多神喻数码的PCP系统
练习题
第十一章近似解的复杂性
11.1胆完全优化问题
11.2PCP和不可近似性
11.3优化问题的归约
11.4难近似的优化问题
练习题
第十二章平均NP-完全性理论
12.1平均易解性
12.2多项式时间归约
12.3p-分布
12.4平均NP-完全问题
12.5扁平分布与随机归约
12.6扁平分布下的完全问题
12.7可抽样分布
练习题
参考文献
名词索引(汉英对照)