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

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