内容提要

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

序言

　　　计 算 复 杂 性 是 计 算 机 理 论 中 极 其 重 要 的 一 个 领 域。它 不 但 包 含 了 一 个 完 整 独 立 而 且 内 容 丰 富 的 理 论， 同 时 也 对 许 多 其 它 有 关 的 计 算 机 和 应 用 数 学 领 域 产 生 了 重 大 的 影 响 。
　　　计 算 复 杂 性 理 论 发 源 于 二 十 世 纪 六 十 年 代， 以 有 多 项 式 时 间 上 界 的 图 灵 机
为 基 本 计 算 模 型 而 奠 定 了 理 论 基 础 。在 七 十 年 代 初 ， 这 门 学 问 由 于 NP-完 全 问 题 的 发 现 而 吸 引 了 人 们 的 注 意 。简 单 地 说 ， 如 果 一 个 问 题 无 法 在 多 项 式 时 间 内 被 确 定 型 图 灵 机 解 决，我 们 称 它 为 难 解} 问 题 。NP-完 全 问 题} 就 是 一 类 直 观 上 难 解 可 是 又 找 不 出 方 法 来 证 明 它 们 的 确 难 解 的 计 算 问 题 。 从 数 学 的 角 度 来 说 ， 这 和 其 它 历 史 上 有 名 的 数 学 问 题 一 样 ， 给 予 人 们 一 个 智 力 上 重 大 的 挑 战 。而 更 重 要 的 是， 在 无 数 与 计 算 有 关 的 学 术 领 域 里 ， NP-完 全 问 题 以 各 种 不 同 形 式 层 出 不 穷。
因 此 ， 这 并 不 是 一 个 纯 粹 的 与 世 独 立 的 智 力 游 戏 ， 而 是 对 计 算 机 科 学 有 全 面 影 响 力 的 问 题 。
　　　人 们 在 七 十 年 代 开 始 对 NP-完 全 问 题 的 研 究 主 要 是 横 向 发 展 ， 也 就 是 以 许 多 不 同 的 计 算 模 型 来 分 析 难 解 问 题 的 本 质 。这 些 新 的 计 算 模 型 包 括 了 平 行 计 算 模 型 、 概 率 计 算 模 型 、 布 尔 线 路 、判 断 树 、 平 均 复 杂 性 、 交 互 证 明 系 统 以 及 程 式 长 度 复 杂 性 等 等 。 对 这 些 新 的 计 算 模 型 的 研 究 一 方 面 使 我 们 对 难 解 问 题 有 了 更 深 一 层 的 认 识 ， 一 方 面 也 产 生 了 一 些 预 想 不 到 的 应 用。最 显 著 的 一 个 例 子 就 是 计 算 密 码 学 的 革 命 性 突 破 ： 基 于 NP 问 题 的 公 钥 密 码 体 系。另 一 个 有 名 的 例 子 是 线 性 规 划 的 多 项 式 时 间 解 的 发 现 。 到 了 八 十 年 代 中 ， 对 NP-完 全 问 题 的 研 究 有 了 纵 向 的 突 破 ， 在 许 多 表 面 看 来 并 不 相 关 的 计 算 模 型 之 间 发 现 了 深 刻 的 刻 划 关 系。这 些 刻 划 关 系 不 但 解 决 了 几 个 令 人 困 扰 多 年 的 未 解 问 题，同 时 也 刺 激 了 其 它 相 关 领 域 的 发 展 。 其 中 之 一 是 对 线 路 复 杂 性 的 研 究 发 现 了 一 些 问 题 在 某 种 有 限 制 的 线 路 模 型 中 必 有 指 数 下 界 。 这 些 结 果 使 用 了 组 合 数 学 与 概 率 方 法 等 新 的 数 学 工 具 ， 并 且 解 决 了 一 个 有 名 的 有 关 多 项 式 分 层 的 未 解 问 题 。 另 一 个 更 重 大 的 结 果 是 以 概 率 可 验 证 明 对 NP类 的 刻 划。由 此 得 出 了 许 多 组 合 优 化 问 题 近 似 解 的 NP-完 全 性，从 而 刺 激 了 算 法 界 对 近 似 算 法 研 究 的 新 热 潮 。这 个 结 果 来 自 于 对 交 互 证 明 系 统 这 个 概 念 的 扩 展， 并 且 使 用 了 线 性 代 数 与 编 码 理 论 等 数 学 证 明 技 巧 。
　　本 书 试 图 对 这 三 十 余 年 来 计 算 复 杂 性 的 研 究 做 一 个 总 结。由 于 以 上 所 介 绍 的 这 门 学 科 的 多 样 性 ， 我 们 在 有 限 的 篇 幅 里 对 这 些 结 果 必 须 有 所 取 舍 。我 们 取 舍 的 原 则 是 以 对 NP-完 全 问 题 有 深 刻 理 解 的 结 果 为 主，并 且 著 重 于 它 们 最 近 的 发 展， 以 期 能 启 发 读 者 在 这 些 方 向 上 有 新 的 发 现 ， 甚 或 发 展 出 更 有 意 义 的 新 方 向 。我 们 对 每 一 个 结 果 都 给 出 完 整 的 数 学 证 明 。由 于 这 些 证 明 使 用 了 许 多 不 同 的 数 学 概 念 与 证 明 技 巧， 这 也 是 一 个 很 好 的 数 学 训 练 。
　　本 书 的 基 本 结 构 如 下 ： 我 们 在 前 四 章 介 绍 计 算 复 杂 性 的 基 本 概 念 与 各 种 复 杂 性 类。在 后 面 八 章 里 ， 我 们 分 别 介 绍 几 个 对 NP-完 全 问 题 的 研 究 方 向。第 五 与 第 六 章 讨 论 NP-完 全 问 题 的 线 路 复 杂 性 和 与 此 相 关 的 NP类 的 内 部 结 构 。第 七 到 第 十 章 对 概 率 计 算 复 杂 性 做 一 个 有 系 统 的 介 绍， 由 较 直 观 的 概 率 计 算 模 型 逐 步 扩 展 到 交 互 证 明 系 统 与 概 率 可 验 证 明 ，最 后 得 到 NP 类 的 一 个 极 为 简 单 而 漂 亮 的 概 率 计 算 刻 划 。第 十 一 章 是 这 个 刻 划 对 NP-完 全 的 优 化 问 题 的 应 用 。 在 第 十 二 章 里 ， 我 们 介 绍 一 个 比 较 新 的 、 正 在 积 极 发 展 中 的 平 均 NP-完 全 性 理 论。这 里 的 平 均 概 念 是 基 于 问 题 实 例 的 概 率 分 布 ， 与 第 七 章 的 概 率 计 算 所 使 用 的 基 于 随 机 数 码 的 概 率 分 布 不 同 ， 因 而 对 NP-完 全 问 题 的 研 究 方 向 也 大 相 径 庭。 (另 外 一 个 与 概 率 计 算 有 深 刻 关 系 的 量 子 计 算 模 型 与 相 关 的 复 杂 性 理 论 ， 由 于 篇 幅 限 制 ， 我 们 不 得 不 在 此 割 舍 。）除 此 之 外 ， 每 一 章 的 练 习 题 里 也 包 含 了 一 些 与 该 章 本 文 有 关 的 %相 关 结 果 。
　　本 书 在 编 写 期 间 得 到 美 国 国 家 科 学 基 金 会 对 第 三 位 作 者 的 资 助(CCR-9820611,
CCR-0296037)，在 此 特 表 感 谢 。

目录

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

作者简介

堵丁柱：1948年生。 中国科学院应用数学所运筹学硕士(1981)。美国加里福利亚大学圣巴巴拉分校数学博士(1985)。美国伯克利数学科学研究所博士后(1985-86)。美国麻省理工学院助理教授(1986-87)。美国普林斯顿大学访问学者(1990-91)。现任 美国明尼苏达大学计算机科学系正教授，中国科学院应用数学所研究员。Journal of Combinatorial Optimization 主编,Book Series of Combinatorial Optimization和 Book Series of Networks Theory and Applications 主编。主要研究方向为组合优化，计算复杂性，算法分析与设计，计算机和通讯网络。发表论文130篇，著书7本。1993年获中国科学院自然科学一等奖。1995年获中国自然科学二等奖。1998年获美国运筹和管理学会CSTC奖（计算机与运筹学边缘科学奖）。

葛可一：1950年生。台湾新竹清华大学数学学士(1972)。 美国俄亥俄州立大学数学硕士(1974)，计算机科学博士(1979)。 现任美国纽约州立大学石溪分校计算机科学系教授。 SIAM Journal on Computing 与 Journal of Complexity 编辑。 曾主持多项美国自然科学基金会研究课题。 主要研究方向为计算复杂性理论，数值计算复杂性和可计算性理论。 发表论文55篇，著书3本。

王　洁：1961年生。中山大学计算机科学系计算数学专业学士(1982)，软件专业硕士(1984)，
美国波士顿大学计算机科学博士(1990)。现任美国麻萨诸塞大学罗威尔分校计算机科学系教授，并任网络与系统安全实验室主任。主要研究方向为平均计算复杂性理论，网络与系统安全，应用算法。曾主持多项美国自然科学基金会的课题及美国英特尔(Intel)公司的课题。发表论文70篇及编书两本。1991年获美国自然科学基金会科研启动奖，2002年获英特尔公司大学项目IXA研究奖。

　　我竭力支持和推荐由堵定柱、葛可一、王洁三位教授合著的《计算复杂性导论》一书。这三位教授是这一领域国际上非常顶尖的学科带头人。堵教授关于复杂性理论的工作（除他关于Steiner 比率的著名工作之外）包括复杂性核心，Boolean线路，是十分深刻和具有影响力的。葛教授来自台湾，除了他在复杂性理论方面的出色研究外，他还是极富才华的作家，出版过几部小说。王在复杂性理论的工作是非常知名的，他还是一位出色的教师。由这三位作者用中文写成的此书是对中国读者的一种奉献。
　　此书涵盖了现代计算复杂性理论，内容从基本的计算复杂性分类到现代的线路复杂性、交互证明、概率复杂性类、近似解的复杂性和平均NP-完全性理论。这三位作者是世界上就这些题目进行论述的最佳人选。这本书总结了计算复杂性理论30多年来的研究成果，我相信它的出版将影响现代计算复杂性理论的发展。
　　此书可用作大学本科生的教材（本书的第一部分），或可用作研究生教材（第二部分）。过去，我发现从中国来的学生对现代计算理论理解较差，理论方面的基础很薄弱。我希望此书将在弥补差距方面发挥巨大作用。中国的现代计算机科学教育一直较弱，在理论课程方面尤其薄弱。我很高兴看到这三位杰出的学者花时间为中国学生写出这样一部佳作。