计算复杂性理论导引

绪论 计算复杂性理论简介 1 0.1 计算复杂性理论的首要问题 1 0.2 计算复杂性理论与算法理论的区别 1 0.3 计算理论及其组成 1 0.4 计算复杂性理论与密码学的关系 2 第1章 计算模型——Turing机 3 1.1 常用术语和记号 3 1.2 Turing机 4 1.2.1 Turing机的基本模型 4 1.2.2 TM的形式化定义 5 1.2.3 TM的格局 5 1.2.4 TM举例 6 1.2.5 描述TM的不同方式 7 1.3 TM的稳健性 8 1.4 ChurchTuring命题 9 1.5 非确定性TM 10 1.6 通用TM 12 习题 12 第2章 计算任务与复杂性 13 2.1 关心的计算任务：判定语言 13 2.2 复杂性的度量 14 2.2.1 大O小o记号 15 2.2.2 时间/空间复杂性的定义 15 2.2.3 两个事实 17 2.2.4 采用大O记号的合理性——带压缩定理和线性加速定理 17 2.2.5 带数目的减少对时间复杂度和空间复杂度的影响 19 2.2.6 DTM与NDTM的时间复杂性关系 20 2.3 复杂性类 20 2.3.1 复杂性类的概念 20 2.3.2 TIME和SPACE之间的平凡(trivial)关系 21 习题 21 第3章 P与NP 23 3.1 P 类 23 3.1.1 P的定义 23 3.1.2 P的重要性 23 3.1.3 P中的问题 24 3.2 NP 类 25 3.2.1 NP的定义 25 3.2.2 NP中的问题 26 3.2.3 世纪难题 P =? NP 27 3.2.4 NP的等价定义 28 3.3 coNP与coNP=? NP 29 习题 31 第4章 归约与NP完全性 32 4.1 历史背景 32 4.2 归约 32 4.2.1 Cook归约 32 4.2.2 Karp归约 33 4.2.3 Levin归约 34 4.3 NP完全性 35 4.4 CookLevin定理 36 4.5 更多NP完全问题 40 4.6 其他NPC问题 43 习题 44 第5章 关于P和NP的更多知识 46 5.1 查找与判定：NPC问题的自归约特性 46 5.1.1 SAT的自归约特性 46 5.1.2 CLIQUE的自归约特性 47 5.1.3 NPC问题都满足自归约特性 48 5.2 NPI语言 49 5.3 P vs NP 50 5.3.1 哈密尔顿回路vs 欧拉回路 50 5.3.2 三色vs四色 51 5.3.3 3SAT vs 2SAT 51 5.4 Oracle TM——相对化 54 习题 56 第6章 对角化方法 57 6.1 对角化方法与不可判定问题的存在性 57 6.1.1 可数集与对角化方法 57 6.1.2 不可判定问题的存在性 58 6.1.3 停机问题不可判定 60 6.2 分层定理 62 6.2.1 空间、时间可构造函数 62 6.2.2 分层定理 63 6.2.3 非确定性时间分层定理 66 6.3 定理A的证明 67 6.4 Ladner定理的证明 69 6.5 复杂性理论常用证明方法总结 70 习题 70 第7章 空间复杂性 72 7.1 PSPACE类 72 7.1.1 Savitch定理 72 7.1.2 PSPACE完全性 74 7.1.3 定理B的证明 76 7.2 L和NL类 77 7.2.1 空间有界的TM 77 7.2.2 L和NL 78 7.2.3 NL完全性 80 7.2.4 NL=coNL 83 习题 85 第8章 随机化算法与随机化复杂性类 87 8.1 随机化算法实例 87 8.1.1 通信复杂性 87 8.1.2 多项式恒等测试 89 8.2 概率图灵机 91 8.3 随机化复杂性类 92 8.3.1 单边错复杂性类：RP和coRP 92 8.3.2 双边错复杂性类：BPP 94 8.3.3 零边错复杂性类：ZPP 96 8.3.4 PP 97 8.4 随机化复杂性类与其他复杂性类之间的关系 99 8.5 素数问题PRIME 101 8.5.1 PRIME∈NP 102 8.5.2 PRIME∈coRP 104 8.5.3 PRIME∈P 105 习题 106 第9章 密码学与复杂性理论 107 9.1 单向函数 107 9.2 伪随机发生器 109 9.3 信息论安全与计算安全 110 第10章 电路复杂性 111 10.1 布尔电路 111 10.2 电路复杂性与P/poly复杂性类 113 10.3 P/poly复杂性类 115 10.4 一致布尔电路 117 10.5 并行计算与Nick复杂性类 118 10.6 BPPP/poly 120 习题 121 第11章 多项式分层 123 11.1 定义与实例 123 11.2 PH的内部结构 124 11.3 交错式TM与PH的等价定义 125 11.4 PH坍塌 127 习题 129 第12章 交互式证明 130 12.1 IP 131 12.2 公开/保密的随机性 133 12.3 IP=PSPACE 135 12.4 零知识证明 141 12.5 概率可验证明(PCP) 143 参考文献 145