目錄

Computational Complexity

出版者的話

譯者序

前言

部分算法

第1章問題與算法

11圖的可達性問題

12流問題

13旅行商問題

14注解、參考文獻和問題

第2章圖靈機

21圖靈機概述

22視為算法的圖靈機

23多帶圖靈機

24線性加速

25空間界

26隨機存取機

27非確定性機

28注解、參考文獻和問題

第3章不可判定性

31通用圖靈機

32停機問題

33更多不可判定性問題

34注解、參考文獻和問題

第二部分邏輯學

第4章布爾邏輯

41布爾表達式

42可滿足性與永真性

43布爾函數與電路

44注解、參考文獻和問題

第5章一階邏輯

51一階邏輯的語法

52模型

53永真的表達式

54公理和證明

55完備性定理

56完備性定理的推論

57二階邏輯

58注解、參考文獻和問題

第6章邏輯中的不可判定性

61數論公理

62作為一個數論概念的計算

63不可判定性與不完備性

64注解、參考文獻和問題

第三部分P和NP

第7章復雜性類之間的關繫

71復雜性類

72譜繫定理

73可達性方法

74注解、參考文獻和問題

第8章歸約和完備性

81歸約

82完全性

83邏輯特征

84注解、參考文獻和問題

第9章NP完全問題

91NP中的問題

92可滿足性問題的不同版本

93圖論問題

94集合和數字

95注解、參考文獻和問題

第10章coNP和函數問題

101NP和coNP

102素性

103函數問題

104注解、參考文獻和問題

第11章隨機計算

111隨機算法

112隨機復雜性類

113隨機源

114電路復雜性

115注解、參考文獻和問題

第12章密碼學

121單向函數

122協議

123注解、參考文獻和問題

第13章可近似性

131近似算法

132近似和復雜性

133不可近似性

134注解、參考文獻和問題

第14章關於P和NP

141NP的地圖

142同構和稠密性

143諭示

144單調電路

145注解、參考文獻和問題

第四部分P內部的計算復雜性類

第15章並行計算

151並行算法

152計算的並行模型

153NC類

154RNC算法

155注解、參考文獻和問題

第16章對數空間

161L=?NL問題

162交錯

163無向圖的可達性

164注解、參考文獻和問題

第五部分NP之外的計算復雜性類

第17章多項式譜繫

171優化問題

172多項式譜繫

173注解、參考文獻和問題

第18章有關計數的計算

181積和式

182P類

183注解、參考文獻和問題

第19章多項式空間

191交錯和博弈

192對抗自然的博弈和交互協議

193更多的PSPACE完全問題

194注解、參考文獻和問題

第20章未來的展望

201指數時間復雜性類

202注解、參考文獻和問題

索引

前言Computational Complexity我僅僅希望簡單敘述請賦予我這一特權因為我們已經被灌輸了帶有這麼多音樂的歌聲音樂正在沉淪而我們的藝術變得如此矯飾以至於裝飾品已經腐蝕了她的容顏是時候說一些簡單的語言了因為明天我們的心靈將起帆遠航——Giorgos Seferis本書適合作為低年級研究生或者高年級本科生學習計算復雜性理論的教材。計算復雜性是計算機科學中思考為什麼有些問題用計算機難以解決的領域。這個領域以前幾乎不存在，而現在卻迅速擴展，並構成了理論計算機科學研究活動的主要內容。現在沒有一本書可以全面介紹復雜性——當然也包括這本書在內。本書隻是包含了我認為可以清楚和相對簡單地表示的結果以及在我看來是復雜性領域的中心內容。



    我認為復雜性是計算(復雜性類)和應用(問題)之間復雜而核心的部分。開篇就向讀者灌輸這一觀點有點為時過早，不過我還是要冒險一試，而且這也將是全書20章中反復強調的觀點。完全性的結論明顯是這一進展的中心環節。邏輯也是如此，它能很好地表達和抓住計算這一概念，是非常重要的應用。因此計算、問題和邏輯是貫穿本書的三大主脈絡。



    內容快速瀏覽目錄，第1章介紹問題和算法——因為當復雜性與簡單性比較時，復雜性好理解。第2章討論圖靈機，同時明確我們的方式將不依賴於機器。第3章介紹非確定性（它不僅是復雜性的形式，而且還具有重大的方法學影響）。



    接著討論邏輯。這一部分可能會被復雜性理論同行視為另類。但是它對於我看待復雜性的觀點非常重要，對於計算機科學非常基本，又很少作為走向計算機科學家的成功之路看待，所以我感到我必須做一次嘗試。第4章介紹布爾邏輯（包括Horn子句的算法屬性，以及布爾電路和香農定理）。第5章介紹一階邏輯及其模型論和證明論，還包括完全性定理，以及足夠的二階邏輯以引出隨後的NP的Fagin特征——非常有用但是往往被忽視，其意義相當於Cook定理。第6章是對Gdel不完全性定理的獨立證明，該證明是邏輯表達計算早期的重要例子。



    然後重點介紹復雜性。第7章介紹已知的復雜性類之間的關繫——包括Savitch和 ImmermanSzelepscényi關於空間復雜性的定理。第8章介紹歸約和完全性概念，緊接著，作為例子，介紹Cook定理和電路值問題的P完全性，同時比較用邏輯表示P和NP的特征。第9章包含很多NP完全的結果，同時介紹各種證明方法。第10章討論coNP和函數問題。第11章介紹隨機算法、與之對應的復雜性類以及用現實隨機源的實現方法。電路和它們與復雜性、隨機化的關繫也在此介紹。第12章很簡短，粗略介紹密碼學和協議。第13章討論近似算法，以及近通過概率可驗證性證明得出的一些不可行性方面的結果。另一方面，第14章討論P=?NP問題的結構性方面，比如，中間度、同構、稠密性和諭示。它還包含了Razborov關於單調電路的下界證明。



    第15章進一步關注P、並行算法及其復雜性，第16章重點討論對數空間，包括無向圖路徑的隨機遊走算法。後，除了NP以外，第17章給出多項式譜繫（包括優化問題的Krentel特征）；第18章講述計數問題和關於積和式的Valiant定理；第19章介紹多項式空間的許多方面（有趣的是關於交互式協議的Shamir定理）；本書後對難解性領域做了簡短展望。



    本書並沒有特別的數學基礎要求——除了要有一定程度的“數學成熟度”，而數學成熟度這個名詞，一般不在序言中給予定義。所有的定理都從基本原理給予證明（除了第13章關於近似性引用了兩個定理外），同時更多的相關結果在每章後一節中說明。證明和構造經常會比文獻裡講述的簡單得多。實際上，本書包含了多個與復雜性相關的主題或專題簡介：基礎數論（用來證明Pratt定理），SolovayStrassen素數測定和RSA密碼協議（第10、11、12章）；基礎概率（第11章和其他章節）；組合數學和概率方法（第10、13、14章）；遞歸理論（第3、14章）；邏輯（第4、5、6章）。由於復雜性問題總是和相對應的算法概念的全面發展聯繫在一起（第1章的有效算法，第11章的隨機算法，第13章的近似算法和第15章的並行算法），所以本書也可以作為算法引論——雖然僅僅粗略分析，但是可以應用在各種情況。



    注解和問題每章的後一節包含了相關的文獻、注解、練習和問題。很多問題涉及更深的結論和課題。就我看來，這是一章中重要的部分（經常也是長的），讀者應該將它作為本書的一部分來閱讀。它經常給出歷史觀點，並把該章放到了更廣泛的領域中。所有這些題目都是可做的，至少在提示下去圖書館查閱答案（我已經發現這樣做至少對我的學生來說，不亞於另一次智商測驗）。對這些題目沒有標記難易，不過對於真正的難題還是給出了警示標記。



    教學本書的重點顯然是復雜性，所以我們將它設計成（以及用作）計算機科學家關於計算理論的入門級讀物。我和我的同事在過去的三年中用它作為加州大學聖地亞哥分校碩士研究生年為期10周的教材。前兩周學習前4章，這些內容對於本科生來說，一般都已熟悉。邏輯學安排在緊接著的3周中，經常省略完全性證明。剩下的5周學習第7章，作為NP完全性的嚴格訓練（不包括在該校的算法課內），選擇第11～14章中的一兩節。一學期的課程可以涵蓋以上4章。如果你想跳過邏輯學部分，可以加上第15章（然而，我相信這樣做會錯過本書相當好的一部分內容）。



    本書至少還可以用於兩門課程：前9章的主題對於計算機科學家很關鍵，所以它可以自豪地替代高年級本科生初級理論課程中的自動機和形式語言（特別是，因為現在的編譯課程都已獨立出來）。我也兩次使用後面的11章作為理論方向的第二學期課程，其目標是帶領有興趣的研究生進入復雜性的研究課題——或者至少幫助他們成為計算機理論會議上見多識廣的聽眾。



    感謝我關於復雜性的想法是我的老師、學生和同事長期鼓舞和啟迪的結果。我非常感謝所有這些人：Ken Steiglitz、Jeff Ullman、Dick Karp、Harry Lewis、John Tsitsiklis、Don Knuth、Steve Vavasis、Jack Edmonds、Albert Meyer、Gary Miller、Patrick Dymond、Paris Kanellakis、David Johnson、Elias Koutsoupias（他也在圖表、後檢查和索引上給予我很多幫助）、Umesh Vazirani、Ken Arrow、Russell Impagliazzo、Sam Buss、Milena Mihail、Vijay Vazirani、Paul Spirakis、Pierluigi Crescenzi、Noga Alon、Stathis Zachos、Heather Woll、Phokion Kolaitis、Neil Immerman、Pete Veinott、Joan Feigenbaum、Lefteris Kirousis、Deng Xiaotie、Foto Afrati、Richard Anderson，主要的是Mihalis Yannakakis和Mike Sipser。他們閱讀了本書的草稿並提出了建設性意見、想法和建議——否則就會讓我為他們的沉默而緊張。在所有對我的課件提出評論的學生中，我記得名字的隻有David Morgenthaller、Goran Gogic、Markus Jacobsson和George Xylomenos（但我記住了其餘人的笑容）。後，感謝Richard Beigel、Matt 、Wenhong Zhu和他們在耶魯的復雜性班，他們找出了本書初稿中的許多錯誤。自然，我對剩下的錯誤負責——盡管我認為我的朋友當初可以找出更多的錯誤。



    我非常感激Martha
Sideri的鼓勵和支持，以及她的注解、看法和封面設計。



    我在加州大學聖地亞哥分校工作時完成本書，但這期間我也訪問了AT&T公司的貝爾實驗室、Bonn大學、Saarbrücken的MaxPlanck研究所、Patras大學和那裡的計算機學院以及巴黎 Sud 大學。我對於算法和復雜性的研究受到美國國家科學基金、Esprit項目AlCOM以及加州大學聖地亞哥分校信息和計算機科學主席Irwin Mark和Joan Klein Jacobs的資助。



    與AddisonWesley的Tom Stone及其同事一起完成本書出版是愉快的。後，我使用了Don Knuth的TeX排版，我的宏是從Jeff Ullman很多年前給我的那些中演變而來的。



    Christos H.Papadimitriou