第1章 引言及預(yù)備知識(shí) 1.1 引言 1.1.1 復(fù)雜性理論概述 1.1.2 復(fù)雜性理論的特征 1.1.3 本書(shū)內(nèi)容概要 1.1.4 寫(xiě)作方法與風(fēng)格 1.1.5 標(biāo)準(zhǔn)符號(hào)及習(xí)慣性用法 1.2 計(jì)算任務(wù)及模型 1.2.1 表達(dá)方式 1.2.2 計(jì)算任務(wù) 1.2.3 一致性模型(算法) 1.2.4 非一致性計(jì)算模型(電路及建議) 1.2.5 復(fù)雜性類(lèi) 本章注釋第2章 p、np和np一完全性 2.1 p-vs-np問(wèn)題 2.1.1 搜索版本：求解與檢驗(yàn) 2.1.2 判定版本：證明與驗(yàn)證 2.1.3 兩種表示的等價(jià)性 2.1.4 對(duì)np的兩個(gè)技術(shù)性說(shuō)明 2.1.5 np的傳統(tǒng)定義 2.1.6 對(duì)p不同于np的支持 2.1.7 哲學(xué)思考 2.2 多項(xiàng)式時(shí)間歸約 2.2.1 歸約的一般概念 2.2.2 優(yōu)化問(wèn)題到搜索問(wèn)題的歸約 2.2.3 搜索問(wèn)題的自歸約性 2.2.4 總結(jié)及一般性觀點(diǎn) 2.3 np.完全性 2.3.1 定義……第3章 p與np的變形第4章 資源越多功能就越強(qiáng)大嗎？第5章 空間復(fù)雜性第6章 隨機(jī)性與計(jì)數(shù)第7章 困難性的用途第8章 偽隨機(jī)數(shù)發(fā)生器第9章 概率證明系統(tǒng)第10章 對(duì)復(fù)雜性要求的弱化附錄a 復(fù)雜性類(lèi)匯總附錄b 尋求下限附錄c 現(xiàn)代密碼學(xué)基礎(chǔ)附錄d 概率論基礎(chǔ)及隨機(jī)性中的前言問(wèn)題附錄e 明確的構(gòu)造附錄f 一些省略的證明附錄g 一些計(jì)算問(wèn)題