計(jì)算復(fù)雜性理論是用數(shù)學(xué)方法研究計(jì)算機(jī)解決各種算法問(wèn)題難易程度的理論。呂克偉編著的《計(jì)算復(fù)雜性理論基礎(chǔ)》對(duì)這一理論的基礎(chǔ)知識(shí)做了全面介紹，力爭(zhēng)幫助讀者掌握該理論的思想方法，為進(jìn)一步開(kāi)展計(jì)算機(jī)科學(xué)的相關(guān)領(lǐng)域的學(xué)習(xí)和研究奠定了基礎(chǔ)。本書(shū)首先介紹計(jì)算復(fù)雜性理論的概述、一些計(jì)算問(wèn)題和邏輯，然后詳細(xì)介紹計(jì)算模型、PvsNP問(wèn)題、歸約和NP完備性理論等；接著針對(duì)信息安全專業(yè)特點(diǎn)，詳細(xì)介紹隨機(jī)化算法、(非)一致電路；最后簡(jiǎn)單介紹幾個(gè)較深入的課題：交互語(yǔ)言類、計(jì)數(shù)復(fù)雜類、概率可驗(yàn)證語(yǔ)言類等。
《計(jì)算復(fù)雜性理論基礎(chǔ)》不僅適合作為計(jì)算機(jī)科學(xué)各專業(yè)高年級(jí)本科生和低年級(jí)研究生(特別是信息安全專業(yè))基礎(chǔ)課教材，也可供有關(guān)研究人員參考。
呂克偉編著的《計(jì)算復(fù)雜性理論基礎(chǔ)》首先介紹計(jì)算復(fù)雜性概述、一些計(jì)算問(wèn)題和邏輯，然后詳細(xì)介紹計(jì)算模型、P vsNP問(wèn)題、歸約和NP完備性理論等；接著針對(duì)信息安全和算法設(shè)計(jì)等專業(yè)特點(diǎn)，詳細(xì)介紹隨機(jī)化算法、(非)一致電路；最后簡(jiǎn)單介紹幾個(gè)較深入的課題：交互語(yǔ)言類、計(jì)數(shù)復(fù)雜類、概率可驗(yàn)證語(yǔ)言類等。我們?cè)噲D通過(guò)對(duì)計(jì)算復(fù)雜性理論的基礎(chǔ)知識(shí)通俗直觀地介紹，幫助讀者掌握該理論的思想方法，為進(jìn)一步開(kāi)展計(jì)算機(jī)科學(xué)的相關(guān)領(lǐng)域的學(xué)習(xí)和研究奠定基礎(chǔ)。因此，本書(shū)不僅適合作為計(jì)算機(jī)科學(xué)各專業(yè)高年級(jí)本科生和低年級(jí)研究生(特別是信息安全專業(yè))基礎(chǔ)課教材，也可供有關(guān)研究人員參考。
第0章 引言
習(xí)題
第1章 一些計(jì)算問(wèn)題
習(xí)題
第2章 邏輯概述
2.1 布爾邏輯
2.2 一階邏輯
2.3 公理和證明
2.4 存在二階邏輯
第3章 計(jì)算模型
3.1 字符串、編碼
3.2 算法時(shí)間的度量與模型
3.3 圖靈機(jī)基礎(chǔ)
3.4 多帶圖靈機(jī)、時(shí)間與空間
3.5 非確定圖靈機(jī)
第0章 引言
習(xí)題
第1章 一些計(jì)算問(wèn)題
習(xí)題
第2章 邏輯概述
2.1 布爾邏輯
2.2 一階邏輯
2.3 公理和證明
2.4 存在二階邏輯
第3章 計(jì)算模型
3.1 字符串、編碼
3.2 算法時(shí)間的度量與模型
3.3 圖靈機(jī)基礎(chǔ)
3.4 多帶圖靈機(jī)、時(shí)間與空間
3.5 非確定圖靈機(jī)
3.6 通用圖靈機(jī)
3.7 遞歸語(yǔ)言與遞歸可枚舉語(yǔ)言
習(xí)題
第4章 不可判定性
4.1 對(duì)角化方法與停機(jī)問(wèn)題
4.2 遞歸可枚舉語(yǔ)言的形式表達(dá)
習(xí)題
第5章 計(jì)算復(fù)雜類
5.1 復(fù)雜類
5.2 分離定理
5.3 可達(dá)性方法
習(xí)題
第6章 歸約和完備性
6.1 歸約
6.2 完備性
6.3 邏輯刻畫(huà)
6.4 NP一關(guān)系
6.5 Oracle圖靈機(jī)
6.6 自歸約
習(xí)題
第7章 NP-完備問(wèn)題、coNP與函數(shù)計(jì)算
7.1 NP-完備問(wèn)題
7.1.1 可滿足問(wèn)題的一些變形
7.1.2 圖論中的NP-完備問(wèn)題
7.1.3 集合與數(shù)
7.2 偽多項(xiàng)式算法和強(qiáng)NP-完備問(wèn)題
7.3 P與NP
7.4 函數(shù)問(wèn)題
7.5 coNP
習(xí)題
第8章 隨機(jī)化計(jì)算
8.1 隨機(jī)化算法
8.1.1 概率素性檢驗(yàn)
8.1.2 符號(hào)行列式
8.1.3 隨機(jī)游動(dòng)
8.2 概率計(jì)算
8.3 RP，coRP，ZPP和PP語(yǔ)言類
8.4 魯棒性
習(xí)題
第9章 電路復(fù)雜度和非一致多項(xiàng)式時(shí)間類
9.1 電路復(fù)雜度
9.2 單調(diào)電路(：Monotone Circuits)
9.3 非一致多項(xiàng)式時(shí)間類(P／Poly)
第10章 幾類語(yǔ)言類介紹
10.1 多項(xiàng)式譜系(I>olynomial Hierarchy)
10.1.1 多項(xiàng)式譜系的定義(PH)
10.1.2 交錯(cuò)圖靈機(jī)與多項(xiàng)式譜系(PH)
10.2 交互證明系統(tǒng)
10.2.1 證明
10.2.2 交互證明系統(tǒng)IP
10.2.3 公共擲幣系統(tǒng)和輪數(shù)
10.3 概率可驗(yàn)證證明系統(tǒng)
10.3.1 PCP系統(tǒng)
10.3.2 PCP系統(tǒng)與交互證明系統(tǒng)
10.3.3 PCP語(yǔ)言
10.3.4 復(fù)雜度度量
10.3.5 PCP系統(tǒng)的相關(guān)結(jié)論
10.4 計(jì)數(shù)類
術(shù)語(yǔ)中英文對(duì)照表
索引
參考文獻(xiàn)
書(shū)單推薦
