第一章　计算模型
  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　AM分层与多项式时间分层
  9.4　IP与AM
  9.5　IP与PSPACE
  练习题
 第十章　概率可验证明
  10.1 PCP的定义
  10.2　NEXPPOLY的PCF特征
   10.2.1　主要证明
   10.2.2　多重线性测试系统
   10.2.3　和检验系统
  10.3 NF的PCP特征
   10.3.1　使用O(logn)个随机数码的PCP系统
   10.3.2　低阶测试系统
   10.3.3　两个PCP系统的复合
   10.3.4　阅读常数多神喻数码的PCP系统
  练习题
 第十一章　近似解的复杂性
  11.1　NP-完全优化问题
  11.2　PCT和不可近似性
  11.3　优化问题的归约
  11.4　难近似的优化问题
  练习题
 第十二章　平均NP-完全性理论
  12.1　平均易解性
  12.2　多项式时间归约
  12.3　P-分布
  12.4　平均NP-完全问题
  12.5　扁平分布与随机归约
  12.6　扁平分布下的完全问题
  12.7　可抽样分布
  练习题
 参考文献
 名词索引（汉英对照）
 Paeface
 Chapter 1 Models of Computation
  1.1 strings,coding and Boolean Functions
  1.2 Deterministic Turing Machines
  1.3 Nondeterministic Turing Machines
  Exercises
 Chapter 2 Complexity Classes
  2.1 Time and Space
  2.2 Universal Turing Machines
  2.3 Diagonalization
  2.4 Simulation
  Exercises
 Chapter 3 NP-completeness
  3.1 NP
  3.2 Cook's Theorem
  3.3　Examples of NP-Complete Problems
  3.4 Polynomial-Time Turing Reducibility
  Exercises
 Chapter 4 Polynomial-Time Hierarchy and Polynomial Space
  4.1 Nondeterministic Oracle Turing Machines
  4.2 Polynomial-Time Hierarchy
  4.3 Complete Problems in PII
  4.4 Alternating Turing Machines
  4.5 PSPACE-Complete Problems
  Exercises
 Chapter 5 Circuit Complexity
  5.1 Bonlaan Circuits
  5.2 Monotone Increasing Functions and Monotone Circuits
  5.3 Parity Function and Constant Depth Circuits
  5.4 Polynomial-Size Boolean Circuits
  Exercises
 Chapter 6 Structure of NP
  6.1 Incomplete Problems in NP
  6.2 One-Way Functions and Cryptography
  6.3 NC
  6.4 P-Completeness
  6.5 Density of NP-Complete Sets
  6.6 Density of EXP-Complete Sets
  Exercises
 Chapter 7 Probabilistic Machines and Complexity Classes
  7.1 Randomized Algorithms
  7.2 Probabilistic Turing Machines and Time Complexity
  7.3 Probabilistic Machines with Bounded Errors
  7.4 PPP,NP and the Polynomial-Time Hierarchy
  Exeicises
 Chapter 8 Complexity of Counting
  8.1 Counting Class #P
  8.2 #P-Complete Problems
  8.3 ⊕P and the Polynomial-Time Hierarchy
  8.4 #P and the Polynomial-Time Hierarchy
  Exeicises
 Chapter 9 Interactive Proof Systems
  9.1 Examples and Definitions
  9.2 Arthur-Merlin Proof Systems
  9.3 AM Hierarchy Versus the Polynomial-Time Hierarchy
  9.4 IP and AM
  9.5 IP and PSPACE
  Exercises
 Chapter 10 Probabilistically Checkable Proofs
  10.1 Definition of PCP
  10.2 PCP Characterization of NEXPPPOLY
   10.2.1 Main Proof
   10.2.2 Multilinearity Test System
   10.2.3 Sum Check System
  10.3 PCP Characterization of NP
   10.3.1 PCP System Using O(logn)Random Bits
   10.3.2 Low-Degree Test System
   10.3.3 Composition of Two PCP Systems
   10.3.4 PCP System Reading a Constant Number of Oracle Bits
  Exercises
 Chapter 11 Complexity of Approximation Problems
  11.1 NP-Complete Optimization Problems
  11.2 PCP and Nonapproximability
  11.3 Reductions Among Optimization Problems
  11.4 Hard-to-Approximate Optimization Problems
  Exercises
 Chapter 12　Theory of Average-Case NP-Completeness
  12.1 Easiness on Average
  12.2 Polynomial-Time Reducibility
  12.3 p-Distributions
  12.4 Average-Case NP-Complete Problems
  12.5 Flat Distributions and Random Reductions
  12.6 Complete Problems Under Flat Distributions
  12.7 Samplable Distributions
  Exercises
 References
 Index