計算復(fù)雜性：現(xiàn)代方法

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