計算復(fù)雜性理論基礎(chǔ)

第0章 引言
習(xí)題
第1章 一些計算問題
習(xí)題
第2章 邏輯概述
2.1 布爾邏輯
2.2 一階邏輯
2.3 公理和證明
2.4 存在二階邏輯
第3章 計算模型
3.1 字符串、編碼
3.2 算法時間的度量與模型
3.3 圖靈機(jī)基礎(chǔ)
3.4 多帶圖靈機(jī)、時間與空間
3.5 非確定圖靈機(jī)
3.6 通用圖靈機(jī)
3.7 遞歸語言與遞歸可枚舉語言
習(xí)題
第4章 不可判定性
4.1 對角化方法與停機(jī)問題
4.2 遞歸可枚舉語言的形式表達(dá)
習(xí)題
第5章 計算復(fù)雜類
5.1 復(fù)雜類
5.2 分離定理
5.3 可達(dá)性方法
習(xí)題
第6章 歸約和完備性
6.1 歸約
6.2 完備性
6.3 邏輯刻畫
6.4 NP一關(guān)系
6.5 Oracle圖靈機(jī)
6.6 自歸約
習(xí)題
第7章 NP-完備問題、coNP與函數(shù)計算
7.1 NP-完備問題
7.1.1 可滿足問題的一些變形
7.1.2 圖論中的NP-完備問題
7.1.3 集合與數(shù)
7.2 偽多項式算法和強(qiáng)NP-完備問題
7.3 P與NP
7.4 函數(shù)問題
7.5 coNP
習(xí)題
第8章 隨機(jī)化計算
8.1 隨機(jī)化算法
8.1.1 概率素性檢驗
8.1.2 符號行列式
8.1.3 隨機(jī)游動
8.2 概率計算
8.3 RP，coRP，ZPP和PP語言類
8.4 魯棒性
習(xí)題
第9章 電路復(fù)雜度和非一致多項式時間類
9.1 電路復(fù)雜度
9.2 單調(diào)電路（Monotone Circuits）
9.3 非一致多項式時間類（P／Poly）
第10章 幾類語言類介紹
10.1 多項式譜系（Dolynomial Hierarchy）
10.1.1 多項式譜系的定義（PH）
10.1.2 交錯圖靈機(jī)與多項式譜系（PH）
10.2 交互證明系統(tǒng)
10.2.1 證明
10.2.2 交互證明系統(tǒng)IP
10.2.3 公共擲幣系統(tǒng)和輪數(shù)
10.3 概率可驗證證明系統(tǒng)
10.3.1 PCP系統(tǒng)
10.3.2 PCP系統(tǒng)與交互證明系統(tǒng)
10.3.3 PCP語言
10.3.4 復(fù)雜度度量
10.3.5 PCP系統(tǒng)的相關(guān)結(jié)論
10.4 計數(shù)類
術(shù)語中英文對照表
索引
參考文獻(xiàn)