編輯推薦

　　計算復雜性理論的研究是計算機科學重要的研究領域之一，而Chistos H. Papadimitriou是該領域知名的專傢之一。

　　計算復雜性是計算機科學中思考為什麼有些問題用計算機難以解決的領域，是理論計算機科學研究的重要內容。復雜性是計算（復雜性類）和應用（問題）之間復雜而核心的部分。

　　本書是一本全麵闡述計算復雜性理論及其近年來進展的教科書，內容頗為深奧，重點介紹復雜性的計算、問題和邏輯。本書主要內容包含算法圖靈機、可計算性等有關計算復雜性理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等復雜性理論的基礎知識；P與NP、NP完全等各復雜性類的概念及其之間的關係等復雜性理論的核心內容；隨機算法、近似算法、並行算法及其復雜性理論；以及NP之外（如多項式空間等）復雜性類的介紹。每章最後一節包括相關的參考文獻、注解、練習和問題，很多問題涉及更深的結論和研究。

內容簡介

　　《計算復雜性：現代方法》係統地介紹計算復雜性理論的經典結果和近30年來取得的新成果，旨在幫助讀者瞭解和掌握復雜性理論中的基本結果、思維方法、主要工具、研究前沿和待決問題。本書分為三部分。*部分（第1～11章）較寬泛地介紹瞭復雜性理論，包括復雜性理論的經典結果和一些現代專題。第二部分（第12～16章）討論瞭各種具體計算模型上的計算復雜性下界。第三部分（第17～23章）主要是1980年以後人們在復雜性理論方麵獲得的進展，內容包括計數復雜性、平均復雜性、難度放大、去隨機化和僞隨機性、PCP定理的證明以及自然證明。本書內容豐富，結構靈活，語言流暢，是從事計算復雜性理論及相關領域的研究人員必不可少的參考書，非常適閤作為打算進入該研究領域的研究生、博士生快速接觸研究前沿的參考資料，還非常適閤作為普通高校計算機科學與技術、數學專業本科生、研究生相關課程的教材，其中的高級專題還可以作為博士生相關討論班的素材。

作者簡介

　　剋裏斯特斯 H. 帕帕季米特裏烏（Christos H. Papadimitriou），是當今計算機科學界最活躍和有影響力的科學傢之一。Papadimitriou擁有普林斯頓大學博士學位，現為加州大學伯剋利分校計算機科學係教授。他曾在哈佛大學、麻省理工學院、雅典工藝大學、斯坦福大學、加州大學聖地亞哥分校任教。他是美國科學院院士、美國工程院院士和美國人文科學院院士。他於2002年獲得高德納奬，2012年獲得哥德爾奬。他的主要研究領域是算法和復雜性，以及它們在優化、數據庫、人工智能、經濟和互聯網等方麵的應用，曾撰寫此領域教科書5本，發錶論文數篇。

目錄

齣版者的話

譯者序

譯者簡介

前言

緻謝

引言

第0章　記號約定1

0.1　對象的字符串錶示1

0.2　判定問題/語言2

0.3　大O記號2

習題3

第一部分　基本復雜性類

第1章　計算模型——為什麼模型選擇無關緊要6

1.1　計算的建模：你真正需要瞭解的內容6

1.2　圖靈機7

1.2.1　圖靈機的錶達能力10

1.3　效率和運行時間11

1.3.1　定義的健壯性11

1.4　機器的位串錶示和通用圖靈機14

1.4.1　通用圖靈機14

1.5　不可計算性簡介15

1.5.1　停機問題16

1.5.2　哥德爾定理17

1.6　類P18

1.6.1　為什麼模型選擇無關緊要19

1.6.2　P的哲學意義19

1.6.3　P的爭議和解決爭議的一些努力20

1.6.4　埃德濛茲的引言21

1.7　定理1.9的證明：O(TlogT)時間的通用模擬21

本章學習內容24

本章注記和曆史24

習題26

第2章　NP和NP完全性29

2.1　類NP29

2.1.1　P和NP的關係31

2.1.2　非確定型圖靈機31

2.2　歸約和NP完全性32

2.3　庫剋勒維定理：計算的局部性34

2.3.1　布爾公式、閤取範式和SAT問題34

2.3.2　庫剋勒維定理34

2.3.3　準備工作：布爾公式的錶達能力35

2.3.4　引理2.11的證明35

2.3.5　將SAT歸約到3SAT38

2.3.6　深入理解庫剋勒維定理38

2.4　歸約網絡39

2.5　判定與搜索42

2.6　coNP、EXP和NEXP43

2.6.1　coNP43

2.6.2　EXP和NEXP44

2.7　深入理解P、NP及其他復雜性類45

2.7.1　NP的哲學意義45

2.7.2　NP與數學證明45

2.7.3　如果P=NP會怎樣45

2.7.4　如果NP=coNP會怎樣46

2.7.5　NP和NP完全之間存在其他復雜性類嗎47

2.7.6　NP難的處理47

2.7.7　更精細的時間復雜性48

本章學習內容48

本章注記和曆史48

習題49

第3章　對角綫方法53

3.1　時間分層定理53

3.2　非確定型時間分層定理54

3.3　拉德納爾定理:NP非完全問題的存在性55

3.4　神喻機器和對角綫方法的局限性57

3.4.1　邏輯獨立與相對59

本章學習內容59

本章注記和曆史59

習題60

第4章　空間復雜性61

4.1　空間受限計算的定義61

4.1.1　格局圖62

4.1.2　一些空間復雜性類63

4.1.3　空間分層定理64

4.2　PSPACE完全性64

4.2.1　塞維奇定理67

4.2.2　PSPACE的本質：*佳博弈策略67

4.3　NL完全性68

4.3.1　基於證明的NL定義:僅能讀一次的證明70

4.3.2　NL=coNL71

本章學習內容72

本章注記和曆史73

習題73

第5章　多項式分層和交錯75

5.1　類Σp275

5.2　多項式分層76

5.2.1　多項式分層的性質76

5.2.2　PH各層的完全問題77

5.3　交錯圖靈機78

5.3.1　無限次交錯79

5.4　時間與交錯：SAT的時空平衡79

5.5　用神喻圖靈機定義多項式分層80

本章學習內容81

本章注記和曆史81

習題82

第6章　布爾綫路83

6.1　布爾綫路和P/poly83

6.1.1　P/poly和P之間的關係85

6.1.2　綫路的可滿足性和庫剋勒維定理的另一種證明86

6.2　一緻綫路87

6.2.1　對數空間一緻綫路族87

6.3　納言圖靈機88

6.4　P/poly和NP88

6.5　綫路下界89

6.6　非一緻分層定理90

6.7　綫路復雜性類的精細分層91

6.7.1　類NC和類AC92

6.7.2　P完全性92

6.8　指數規模的綫路93

本章學習內容93

本章注記和曆史94

習題94

第7章　隨機計算96

7.1　概率型圖靈機97

7.2　概率型圖靈機示例98

7.2.1　尋找中位數99

7.2.2　概率型素性測試100

7.2.3　多項式恒等測試101

7.2.4　二分圖的完美匹配測試102

7.3　單麵錯誤和“零麵”錯誤：RP、coRP、ZPP103

7.4　定義的健壯性103

7.4.1　準確度常數的作用：錯率歸約104

7.4.2　期望運行時間與*壞運行時間105

7.4.3　使用比均勻硬幣投擲更具一般性的隨機選擇106

7.5　BPP同其他復雜性類之間的關係106

7.5.1　BPP�罰/poly107

7.5.2　BPP�罰H107

7.5.3　分層定理與完全問題108

7.6　隨機歸約109

7.7　空間受限的隨機計算109

本章學習內容110

本章注記和曆史110

習題111

第8章　交互式證明113

8.1　交互式證明及其變形113

8.1.1　準備工作：驗證者和證明者均為確定型的交互式證明113

8.1.2　類IP：概率型驗證者115

8.1.3　圖不同構的交互式證明116

8.2　公用隨機源和類AM118

8.2.1　私有隨機源的模擬119

8.2.2　集閤下界協議120

8.2.3　定理8.12的證明概要123

8.2.4　GI能是NP�餐耆�的嗎123

8.3　IP=PSPACE124

8.3.1　算術化125

8.3.2　#SATD的交互式協議125

8.3.3　TQBF的協議：定理8.19的證明127

8.4　證明者的能力128

8.5　多證明者交互式證明129

8.6　程序檢驗130

8.6.1　具有驗證程序的語言131

8.6.2　隨機自歸約與積和式131

8.7　積和式的交互式證明132

8.7.1　協議133

本章學習內容134

本章注記和曆史134

習題135

第9章　密碼學137

9.1　完全保密及其局限性138

9.2　計算安全、單嚮函數和僞隨機數産生器139

9.2.1　單嚮函數：定義和實例141

9.2.2　用單嚮函數實現加密142

9.2.3　僞隨機數産生器143

9.3　用單嚮置換構造僞隨機數産生器144

9.3.1　不可預測性蘊含僞隨機性144

9.3.2　引理9.10的證明：戈德賴希勒維定理145

9.4　零知識149

9.5　應用151

9.5.1　僞隨機函數及其應用151

9.5.2　去隨機化153

9.5.3　電話投幣和比特承諾154

9.5.4　安全的多方計算154

9.5.5　機器學習的下界155

本章學習內容155

本章注記和曆史155

習題158

第10章　量子計算161

10.1　量子怪相：雙縫實驗162

10.2　量子疊加和量子位163

10.2.1　EPR悖論165

10.3　量子計算的定義和BQP168

10.3.1　綫性代數預備知識168

10.3.2　量子寄存器及其狀態嚮量168

10.3.3　量子操作169

10.3.4　量子操作實例169

10.3.5　量子計算與BQP171

10.3.6　量子綫路172

10.3.7　傳統計算是量子計算的特例173

10.3.8　通用操作173

10.4　格羅弗搜索算法174

10.5　西濛算法177

10.5.1　定理10.14的證明177

10.6　肖爾算法:用量子計算機實現整數分解178

10.6.1　ZM上的傅裏葉變換179

10.6.2　ZM上的量子傅裏葉變換180

10.6.3　肖爾的階發現算法181

10.6.4　因數分解歸約為階發現184

10.6.5　實數的有理數近似185

10.7　BQP和經典復雜性類186

10.7.1　量子計算中類似於NP和AM的復雜性類187

本章學習內容187

本章注記和曆史188

習題190

第11章　PCP定理和近似難度簡介192

11.1　動機：近似求解NP難的優化問題193

11.2　用兩種觀點理解PCP定理194

11.2.1　PCP定理與局部可驗證明194

11.2.2　PCP定理與近似難度197

11.3　兩種觀點的等價性197

11.3.1　定理11.5與定理11.9的等價性198

11.3.2　重新審視PCP的兩種理解199

11.4　頂點覆蓋問題和獨立集問題的近似難度200

11.5　NP�罰CP(poly(n),1):由沃爾什哈達瑪編碼得到的PCP202

11.5.1　綫性測試與沃爾什哈達瑪編碼202

11.5.2　定理11.19的證明203

本章學習內容206

本章注記和曆史206

習題207

第二部分　具體計算模型的下界

第12章　判定樹210

12.1　判定樹和判定樹復雜性210

12.2　證明復雜性212

12.3　隨機判定樹213

12.4　證明判定樹下界的一些技術214

12.4.1　隨機復雜性的下界214

12.4.2　敏感性215

12.4.3　次數方法216

本章學習內容217

本章注記和曆史217

習題218

第13章　通信復雜性219

13.1　雙方通信復雜性的定義219

13.2　下界方法220

13.2.1　詐集方法220

13.2.2　鋪砌方法221

13.2.3　秩方法222

13.2.4　差異方法223

13.2.5　證明差異上界的一種技術223

13.2.6　各種下界方法的比較224

13.3　多方通信復雜性225

13.4　其他通信復雜性模型概述227

本章學習內容228

本章注記和曆史228

習題229

第14章　綫路下界：復雜性理論的滑鐵盧232

14.1　AC0和哈斯塔德開關引理232

14.1.1　哈斯塔德開關引理233

14.1.2　開關引理的證明234

14.2　帶“計數器”的綫路:ACC236

14.3　單調綫路的下界239

14.3.1　定理14.7的證明239

14.4　綫路復雜性的前沿242

14.4.1　用對角綫方法證明綫路下界242

14.4.2　ACC Vs P的研究現狀243

14.4.3　具有對數深度的綫性綫路244

14.4.4　綫路圖244

14.5　通信復雜性方法245

14.5.1　與ACC0綫路之間的聯係245

14.5.2　與綫性規模對數深度的綫路之間的聯係246

14.5.3　與綫路圖之間的聯係246

14.5.4　卡奇梅爾維格德爾森通信遊戲

與深度下界246

本章學習內容248

本章注記和曆史249

習題249

第15章　證明復雜性251

15.1　幾個例子251

15.2　命題演算與歸結252

15.2.1　用瓶頸法證明下界253

15.2.2　插值定理和歸結的指數下界254

15.3　其他證明係統概述256

15.4　元數學的思考258

本章學習內容258

本章注記和曆史258

習題259

第16章　代數計算模型260

16.1　代數直綫程序和代數綫路261

16.1.1　代數直綫程序261

16.1.2　例子262

16.1.3　代數綫路263

16.1.4　代數綫路中類似於P、NP的復雜性類264

16.2　代數計算樹266

16.2.1　下界的拓撲方法268

16.3　布盧姆舒布斯梅爾模型270

16.3.1　復數上的復雜性類271

16.3.2　完全問題和希爾伯特零點定理271

16.3.3　判定性問題——曼德勃羅集272

本章學習內容272

本章注記和曆史273

習題274

第三部分　高級專題

第17章　計數復雜性278

17.1　計數問題舉例278

17.1.1　計數問題與概率估計279

17.1.2　計數可能難於判定279

17.2　復雜性類#P280

17.2.1　復雜性類PP：類似於#P的判定問題281

17.3　#P完全性281

17.3.1　積和式和瓦利安特定理282

17.3.2　#P問題的近似解286

17.4　戶田定理：PH�罰#SAT287

17.4.1　過渡：具有唯一解的布爾滿足性問題288

17.4.2　?的性質和對NP、coNP證明引理17.17289

17.4.3　引理17.17的證明：一般情形290

17.4.4　第二步：轉換為確定型歸約291

17.5　待決問題292

本章學習內容293

本章注記和曆史293

習題293

第18章　平均復雜性:勒維定理295

18.1　分布問題與distP296

18.2　“實際分布”的形式化定義298

18.3　distNP及其完全問題298

18.3.1　distNP的一個完全問題300

18.3.2　P�部沙檠�的分布301

18.4　哲學意義和實踐意義301

本章學習內容303

本章注記和曆史303

習題303

第19章　難度放大和糾錯碼305

19.1　從溫和難度到強難度：姚期智XOR引理306

19.1.1　用因帕利亞佐難度核引理證明姚期智XOR引理307

19.1.2　因帕利亞佐難度核引理的證明309

19.2　工具：糾錯碼310

19.2.1　顯式糾錯碼312

19.2.2　沃爾什哈達瑪糾錯碼312

19.2.3　裏德所羅門糾錯碼313

19.2.4　裏德穆勒糾錯碼313

19.2.5　拼接糾錯碼314

19.3　高效解碼315

19.3.1　裏德所羅門解碼315

19.3.2　拼接解碼316

19.4　局部解碼與難度放大316

19.4.1　沃爾什哈達瑪糾錯碼的局部解碼算法318

19.4.2　裏德穆勒糾錯碼的局部解碼算法318

19.4.3　拼接糾錯碼的局部解碼算法319

19.4.4　局部解碼算法綜閤運用於難度放大320

19.5　列錶解碼321

19.5.1　裏德所羅門糾錯碼的列錶解碼322

19.6　局部列錶解碼：接近BPP=P323

19.6.1　沃爾什哈達瑪糾錯碼的局部列錶解碼323

19.6.2　裏德穆勒糾錯碼的局部列錶解碼323

19.6.3　拼接糾錯碼的局部列錶解碼325

19.6.4　局部列錶解碼算法綜閤運用於難度放大325

本章學習內容326

本章注記 計算復雜性：現代方法 下載 mobi epub pdf txt 電子書

不錯，快遞給力。正在做相關方麵的研究，本書可做參考。

大部頭著作啊!

不錯

好評。。。。。。。

包裝很好內容很贊我很喜歡

查閱用，還要花時間好好啃

不錯，挺好，速度超快，支持京東

還行啊，就是看不懂。。。。

很厚的一本書，有時間好好學一學