計算復雜性：現代方法

出版者的話譯者序譯者簡介前言致謝引言第0章　記號約定10.1　對象的字符串表示10.2　判定問題/語言20.3　大O記號2習題3第一部分　基本復雜性類第1章　計算模型——為什么模型選擇無關緊要61.1　計算的建模：你真正需要了解的內容61.2　圖靈機71.2.1　圖靈機的表達能力101.3　效率和運行時間111.3.1　定義的健壯性111.4　機器的位串表示和通用圖靈機141.4.1　通用圖靈機141.5　不可計算性簡介151.5.1　停機問題161.5.2　哥德爾定理171.6　類P181.6.1　為什么模型選擇無關緊要191.6.2　P的哲學意義191.6.3　P的爭議和解決爭議的一些努力201.6.4　埃德蒙茲的引言211.7　定理1.9的證明：O(TlogT)時間的通用模擬21本章學習內容24本章注記和歷史24習題26第2章　NP和NP完全性292.1　類NP292.1.1　P和NP的關系312.1.2　非確定型圖靈機312.2　歸約和NP完全性322.3　庫克勒維定理：計算的局部性342.3.1　布爾公式、合取范式和SAT問題342.3.2　庫克勒維定理342.3.3　準備工作：布爾公式的表達能力352.3.4　引理2.11的證明352.3.5　將SAT歸約到3SAT382.3.6　深入理解庫克勒維定理382.4　歸約網絡392.5　判定與搜索422.6　coNP、EXP和NEXP432.6.1　coNP432.6.2　EXP和NEXP442.7　深入理解P、NP及其他復雜性類452.7.1　NP的哲學意義452.7.2　NP與數學證明452.7.3　如果P=NP會怎樣452.7.4　如果NP=coNP會怎樣462.7.5　NP和NP完全之間存在其他復雜性類嗎472.7.6　NP難的處理472.7.7　更精細的時間復雜性48本章學習內容48本章注記和歷史48習題49第3章　對角線方法533.1　時間分層定理533.2　非確定型時間分層定理543.3　拉德納爾定理:NP非完全問題的存在性553.4　神喻機器和對角線方法的局限性573.4.1　邏輯獨立與相對59本章學習內容59本章注記和歷史59習題60第4章　空間復雜性614.1　空間受限計算的定義614.1.1　格局圖624.1.2　一些空間復雜性類634.1.3　空間分層定理644.2　PSPACE完全性644.2.1　塞維奇定理674.2.2　PSPACE的本質：*佳博弈策略674.3　NL完全性684.3.1　基于證明的NL定義:僅能讀一次的證明704.3.2　NL=coNL71本章學習內容72本章注記和歷史73習題73第5章　多項式分層和交錯755.1　類Σp2755.2　多項式分層765.2.1　多項式分層的性質765.2.2　PH各層的完全問題775.3　交錯圖靈機785.3.1　無限次交錯795.4　時間與交錯：SAT的時空平衡795.5　用神喻圖靈機定義多項式分層80本章學習內容81本章注記和歷史81習題82第6章　布爾線路836.1　布爾線路和P/poly836.1.1　P/poly和P之間的關系856.1.2　線路的可滿足性和庫克勒維定理的另一種證明866.2　一致線路876.2.1　對數空間一致線路族876.3　納言圖靈機886.4　P/poly和NP886.5　線路下界896.6　非一致分層定理906.7　線路復雜性類的精細分層916.7.1　類NC和類AC926.7.2　P完全性926.8　指數規(guī)模的線路93本章學習內容93本章注記和歷史94習題94第7章　隨機計算967.1　概率型圖靈機977.2　概率型圖靈機示例987.2.1　尋找中位數997.2.2　概率型素性測試1007.2.3　多項式恒等測試1017.2.4　二分圖的完美匹配測試1027.3　單面錯誤和“零面”錯誤：RP、coRP、ZPP1037.4　定義的健壯性1037.4.1　準確度常數的作用：錯率歸約1047.4.2　期望運行時間與*壞運行時間1057.4.3　使用比均勻硬幣投擲更具一般性的隨機選擇1067.5　BPP同其他復雜性類之間的關系1067.5.1　BPPP/poly1077.5.2　BPPPH1077.5.3　分層定理與完全問題1087.6　隨機歸約1097.7　空間受限的隨機計算109本章學習內容110本章注記和歷史110習題111第8章　交互式證明1138.1　交互式證明及其變形1138.1.1　準備工作：驗證者和證明者均為確定型的交互式證明1138.1.2　類IP：概率型驗證者1158.1.3　圖不同構的交互式證明1168.2　公用隨機源和類AM1188.2.1　私有隨機源的模擬1198.2.2　集合下界協議1208.2.3　定理8.12的證明概要1238.2.4　GI能是NP完全的嗎1238.3　IP=PSPACE1248.3.1　算術化1258.3.2　#SATD的交互式協議1258.3.3　TQBF的協議：定理8.19的證明1278.4　證明者的能力1288.5　多證明者交互式證明1298.6　程序檢驗1308.6.1　具有驗證程序的語言1318.6.2　隨機自歸約與積和式1318.7　積和式的交互式證明1328.7.1　協議133本章學習內容134本章注記和歷史134習題135第9章　密碼學1379.1　完全保密及其局限性1389.2　計算安全、單向函數和偽隨機數產生器1399.2.1　單向函數：定義和實例1419.2.2　用單向函數實現加密1429.2.3　偽隨機數產生器1439.3　用單向置換構造偽隨機數產生器1449.3.1　不可預測性蘊含偽隨機性1449.3.2　引理9.10的證明：戈德賴希勒維定理1459.4　零知識1499.5　應用1519.5.1　偽隨機函數及其應用1519.5.2　去隨機化1539.5.3　電話投幣和比特承諾1549.5.4　安全的多方計算1549.5.5　機器學習的下界155本章學習內容155本章注記和歷史155習題158第10章　量子計算16110.1　量子怪相：雙縫實驗16210.2　量子疊加和量子位16310.2.1　EPR悖論16510.3　量子計算的定義和BQP16810.3.1　線性代數預備知識16810.3.2　量子寄存器及其狀態(tài)向量16810.3.3　量子操作16910.3.4　量子操作實例16910.3.5　量子計算與BQP17110.3.6　量子線路17210.3.7　傳統計算是量子計算的特例17310.3.8　通用操作17310.4　格羅弗搜索算法17410.5　西蒙算法17710.5.1　定理10.14的證明17710.6　肖爾算法:用量子計算機實現整數分解17810.6.1　ZM上的傅里葉變換17910.6.2　ZM上的量子傅里葉變換18010.6.3　肖爾的階發(fā)現算法18110.6.4　因數分解歸約為階發(fā)現18410.6.5　實數的有理數近似18510.7　BQP和經典復雜性類18610.7.1　量子計算中類似于NP和AM的復雜性類187本章學習內容187本章注記和歷史188習題190第11章　PCP定理和近似難度簡介19211.1　動機：近似求解NP難的優(yōu)化問題19311.2　用兩種觀點理解PCP定理19411.2.1　PCP定理與局部可驗證明19411.2.2　PCP定理與近似難度19711.3　兩種觀點的等價性19711.3.1　定理11.5與定理11.9的等價性19811.3.2　重新審視PCP的兩種理解19911.4　頂點覆蓋問題和獨立集問題的近似難度20011.5　NPPCP(poly(n),1):由沃爾什哈達瑪編碼得到的PCP20211.5.1　線性測試與沃爾什哈達瑪編碼20211.5.2　定理11.19的證明203本章學習內容206本章注記和歷史206習題207第二部分　具體計算模型的下界第12章　判定樹21012.1　判定樹和判定樹復雜性21012.2　證明復雜性21212.3　隨機判定樹21312.4　證明判定樹下界的一些技術21412.4.1　隨機復雜性的下界21412.4.2　敏感性21512.4.3　次數方法216本章學習內容217本章注記和歷史217習題218第13章　通信復雜性21913.1　雙方通信復雜性的定義21913.2　下界方法22013.2.1　詐集方法22013.2.2　鋪砌方法22113.2.3　秩方法22213.2.4　差異方法22313.2.5　證明差異上界的一種技術22313.2.6　各種下界方法的比較22413.3　多方通信復雜性22513.4　其他通信復雜性模型概述227本章學習內容228本章注記和歷史228習題229第14章　線路下界：復雜性理論的滑鐵盧23214.1　AC0和哈斯塔德開關引理23214.1.1　哈斯塔德開關引理23314.1.2　開關引理的證明23414.2　帶“計數器”的線路:ACC23614.3　單調線路的下界23914.3.1　定理14.7的證明23914.4　線路復雜性的前沿24214.4.1　用對角線方法證明線路下界24214.4.2　ACC Vs P的研究現狀24314.4.3　具有對數深度的線性線路24414.4.4　線路圖24414.5　通信復雜性方法24514.5.1　與ACC0線路之間的聯系24514.5.2　與線性規(guī)模對數深度的線路之間的聯系24614.5.3　與線路圖之間的聯系24614.5.4　卡奇梅爾維格德爾森通信游戲與深度下界246本章學習內容248本章注記和歷史249習題249第15章　證明復雜性25115.1　幾個例子25115.2　命題演算與歸結25215.2.1　用瓶頸法證明下界25315.2.2　插值定理和歸結的指數下界25415.3　其他證明系統概述25615.4　元數學的思考258本章學習內容258本章注記和歷史258習題259第16章　代數計算模型26016.1　代數直線程序和代數線路26116.1.1　代數直線程序26116.1.2　例子26216.1.3　代數線路26316.1.4　代數線路中類似于P、NP的復雜性類26416.2　代數計算樹26616.2.1　下界的拓撲方法26816.3　布盧姆舒布斯梅爾模型27016.3.1　復數上的復雜性類27116.3.2　完全問題和希爾伯特零點定理27116.3.3　判定性問題——曼德勃羅集272本章學習內容272本章注記和歷史273習題274第三部分　高級專題第17章　計數復雜性27817.1　計數問題舉例27817.1.1　計數問題與概率估計27917.1.2　計數可能難于判定27917.2　復雜性類#P28017.2.1　復雜性類PP：類似于#P的判定問題28117.3　#P完全性28117.3.1　積和式和瓦利安特定理28217.3.2　#P問題的近似解28617.4　戶田定理：PHP#SAT28717.4.1　過渡：具有唯一解的布爾滿足性問題28817.4.2　?的性質和對NP、coNP證明引理17.1728917.4.3　引理17.17的證明：一般情形29017.4.4　第二步：轉換為確定型歸約29117.5　待決問題292本章學習內容293本章注記和歷史293習題293第18章　平均復雜性:勒維定理29518.1　分布問題與distP29618.2　“實際分布”的形式化定義29818.3　distNP及其完全問題29818.3.1　distNP的一個完全問題30018.3.2　P可抽樣的分布30118.4　哲學意義和實踐意義301本章學習內容303本章注記和歷史303習題303第19章　難度放大和糾錯碼30519.1　從溫和難度到強難度：姚期智XOR引理30619.1.1　用因帕利亞佐難度核引理證明姚期智XOR引理30719.1.2　因帕利亞佐難度核引理的證明30919.2　工具：糾錯碼31019.2.1　顯式糾錯碼31219.2.2　沃爾什哈達瑪糾錯碼31219.2.3　里德所羅門糾錯碼31319.2.4　里德穆勒糾錯碼31319.2.5　拼接糾錯碼31419.3　高效解碼31519.3.1　里德所羅門解碼31519.3.2　拼接解碼31619.4　局部解碼與難度放大31619.4.1　沃爾什哈達瑪糾錯碼的局部解碼算法31819.4.2　里德穆勒糾錯碼的局部解碼算法31819.4.3　拼接糾錯碼的局部解碼算法31919.4.4　局部解碼算法綜合運用于難度放大32019.5　列表解碼32119.5.1　里德所羅門糾錯碼的列表解碼32219.6　局部列表解碼：接近BPP=P32319.6.1　沃爾什哈達瑪糾錯碼的局部列表解碼32319.6.2　里德穆勒糾錯碼的局部列表解碼32319.6.3　拼接糾錯碼的局部列表解碼32519.6.4　局部列表解碼算法綜合運用于難度放大325本章學習內容326本章注記和歷史327習題328第20章　去隨機化33020.1　偽隨機數產生器和去隨機化33120.1.1　用偽隨機數產生器實現去隨機化33120.1.2　難度與去隨機化33320.2　定理20.6的證明：尼散維格德爾森構造33420.2.1　兩個示意性例子33420.2.2　尼散維格德爾森構造33620.3　一致假設下的去隨機化33920.4　去隨機化需要線路下界340本章學習內容343本章注記和歷史343習題344第21章　偽隨機構造:擴張圖和提取器34521.1　隨機游走和特征值34621.1.1　分布向量和參數λ(G)34621.1.2　無向連通性問題的隨機算法的分析34921.2　擴張圖34921.2.1　代數定義35021.2.2　組合擴張和擴張圖的存在性35021.2.3　代數擴張圖蘊含組合擴張圖35121.2.4　組合擴張圖蘊含代數擴張圖35221.2.5　用擴張圖設計糾錯碼35321.3　擴張圖的顯式構造35521.3.1　旋轉映射35621.3.2　矩陣乘積和路徑乘積35621.3.3　張量積35621.3.4　替換乘積35721.3.5　顯式構造35921.4　無向連通性問題的確定型對數空間算法36121.4.1　連通性問題的對數空間算法（定理21.21的證明）36121.5　弱隨機源和提取器36221.5.1　*小熵36321.5.2　統計距離36421.5.3　隨機性提取器的定義36421.5.4　提取器的存在性證明36421.5.5　基于哈希函數構造提取器36521.5.6　基于擴張圖的隨機游走構造提取器36621.5.7　由偽隨機數產生器構造提取器36621.6　空間受限計算的偽隨機數產生器368本章學習內容372本章注記和歷史372習題374第22章　PCP定理的證明和傅里葉變換技術37822.1　非二進制字母表上的約束滿足問題37822.2　PCP定理的證明37922.2.1　PCP定理的證明思路37922.2.2　迪納爾鴻溝放大：引理22.5的證明38022.2.3　擴張圖、隨機游走和INDSET的近似難度38122.2.4　迪納爾鴻溝放大38222.2.5　字母表削減：引理22.6的證明38722.3　2CSPW的難度：鴻溝和字母表大小之間的平衡38922.3.1　萊斯的證明思想：并行重復38922.4　哈斯塔德3位PCP定理和MAX3SAT的難度39022.4.1　MAX3SAT的近似難度39022.5　工具：傅里葉變換39122.5.1　GF(2)n上的傅里葉變換39122.5.2　從較高層面看傅里葉變換和PCP之間的聯系39322.5.3　GF(2)上線性測試的分析39322.6　坐標函數、長編碼及其測試39522.7　定理22.16的證明39622.8　SETCOVER的近似難度40022.9　其他PCP定理概述40222.9.1　具有亞常數可靠性參數的PCP定理40222.9.2　平攤的查驗復雜度40222.9.3　2位測試和高效傅里葉分析40322.9.4　唯一性游戲和閾值結果40422.9.5　與等周問題和度量空間嵌入之間的聯系40422.A　將qCSP實例轉換成“精細”實例405本章學習內容406本章注記和歷史407習題408第23章　為什么線路下界如此困難41123.1　自然證明的定義41123.2　為什么自然證明是自然的41223.2.1　為什么要求可構造性41323.2.2　為什么要求廣泛性41323.2.3　用復雜性測度看自然證明41423.3　定理23.1的證明41523.4　一個“不自然的”下界41623.5　哲學觀點417本章注記和歷史417習題418附錄A　數學基礎419部分習題的提示438參考文獻447術語索引472復雜性類索引478