唐常杰翻譯的計(jì)算理論導(dǎo)引23課件

Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可以從下列文件獲得ＰPT素材：

13_10-復(fù)雜理論高級(jí)專題-同學(xué)報(bào)告素材.doc本章提綱10.1近似算法、10.2概率算法10.3交錯(cuò)式10.4交互證明，10.5并行計(jì)算10.6密碼學(xué)2022/12/281Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可根據(jù)

提供的ＰPT素材+參考以前同學(xué)的報(bào)告，

修改成為有自己見(jiàn)解的討論報(bào)告

建議：

底色用淺色（象牙白，淺黃，白色等）

適合色盲色弱觀眾

字體顏色選擇余地大

在投影機(jī)效果差時(shí)也還能能看見(jiàn)

2022/12/282Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可近似算法在最優(yōu)化問(wèn)題中，通常試圖在可行解中尋找最好的解，即最優(yōu)解。在實(shí)踐中，可能并不一定非要最優(yōu)解不可，一個(gè)接近最優(yōu)的解可能是足夠好的，而且可能更容易找到。近似算法是為了求近似最優(yōu)解而設(shè)計(jì)的。2022/12/283近似算法在最優(yōu)化問(wèn)題中，通常試圖在可行解中尋找最好的解，即最頂點(diǎn)覆蓋問(wèn)題若G是無(wú)向圖，則G的頂點(diǎn)覆蓋是節(jié)點(diǎn)的一個(gè)子集，使得G的每條邊都與子集中的節(jié)點(diǎn)之一相關(guān)聯(lián)。2022/12/284頂點(diǎn)覆蓋問(wèn)題若G是無(wú)向圖，則G的頂點(diǎn)覆蓋是節(jié)點(diǎn)的一個(gè)子集，使最小頂點(diǎn)覆蓋的一個(gè)近似算法下述多項(xiàng)式時(shí)間算法近似地解這個(gè)最優(yōu)化問(wèn)題，它給出一個(gè)頂點(diǎn)覆蓋，其大小不超過(guò)最小頂點(diǎn)覆蓋的大小的2倍。A＝“對(duì)于輸入<G>，這里G是一個(gè)無(wú)向圖：重復(fù)下述操作直至G中所有的邊都與有標(biāo)記的邊相鄰。在G中找一條不與任何有標(biāo)記的邊相鄰的邊。給這條邊作標(biāo)記。輸出所有有標(biāo)記邊的頂點(diǎn)。”2022/12/285最小頂點(diǎn)覆蓋的一個(gè)近似算法下述多項(xiàng)式時(shí)間算法近似地解這個(gè)最優(yōu)定理1０.1定理11.1：A是一個(gè)多項(xiàng)式時(shí)間算法，它給出G的一個(gè)頂點(diǎn)覆蓋，其大小不超過(guò)最小頂點(diǎn)覆蓋的大小的2倍。證明思路:A的運(yùn)行時(shí)間顯然是多項(xiàng)式界限的。設(shè)X是它輸出的頂點(diǎn)集合，H是有標(biāo)記的邊的集合。因?yàn)镚的每一條邊要么屬于H，要么與H中的一條邊相鄰，因此X與G的所有邊關(guān)聯(lián)，因此X是一個(gè)頂點(diǎn)覆蓋。證明X的大小不超過(guò)最小頂點(diǎn)覆蓋Y的大小的2倍。X的大小是H的2倍H不大于Y2022/12/286定理1０.1定理11.1：A是一個(gè)多項(xiàng)式時(shí)間算法，它給出G的k-優(yōu)算法如果一個(gè)最小化問(wèn)題的近似算法總能找到不超過(guò)最優(yōu)解k倍的可行解，則稱這個(gè)算法是k-優(yōu)的。對(duì)于最大化問(wèn)題，一個(gè)k-優(yōu)近似算法總能找到不小于最優(yōu)解大小的1/k的可行解。2022/12/287k-優(yōu)算法如果一個(gè)最小化問(wèn)題的近似算法總能找到不超過(guò)最優(yōu)解k最大割集的近似算法把頂點(diǎn)集V劃分成兩個(gè)不相交的子集S和T，稱為無(wú)向圖中的割。頂點(diǎn)分別在兩個(gè)子集中的邊稱為割邊，割邊的數(shù)目稱為割的大小。B＝“對(duì)于輸入<G>，這里G是頂點(diǎn)集為V的無(wú)向圖：令S＝?和T＝V。如果把一個(gè)頂點(diǎn)從S移到T或者從T移到S，使割的大小變大，則做這樣的移動(dòng)，并且重復(fù)這一步。如果不存在這樣的頂點(diǎn)，則輸出當(dāng)前的割并且停止?！?022/12/288最大割集的近似算法把頂點(diǎn)集V劃分成兩個(gè)不相交的子集S和T，稱定理1０.2定理11.2：B是最大割集的2-優(yōu)的多項(xiàng)式近似算法。證明：割的大小不超過(guò)G的邊數(shù)，故B是多項(xiàng)式時(shí)間的。證明B輸出的割X至少包含G中的所有邊的一半。X的每個(gè)頂點(diǎn)的割邊>=非割邊。X的所有頂點(diǎn)的割邊數(shù)和＝X的割邊總數(shù)×2。X的所有頂點(diǎn)的非割邊數(shù)和＝X的非割邊總數(shù)×2。X的割邊數(shù)和>=X的非割邊數(shù)和X的割邊數(shù)>=G的所有邊數(shù)/2

G的所有邊數(shù)>=最大割邊數(shù)2022/12/289定理1０.2定理11.2：B是最大割集的2-優(yōu)的多項(xiàng)式近似算概率算法概率算法使用隨機(jī)過(guò)程的結(jié)果。典型包含一條“扔硬幣”的指令，并且扔硬幣的結(jié)果可能影響算法后面的執(zhí)行和輸出。BPP類素?cái)?shù)性只讀一次的分支程序2022/12/2810概率算法概率算法使用隨機(jī)過(guò)程的結(jié)果。典型包含一條“扔硬幣”的概率圖靈機(jī)概率圖靈機(jī)M是一種非確定型圖靈機(jī)，它的每一非確定步，稱作擲硬幣步，并且有兩個(gè)合法的下次動(dòng)作。定義分支b的概率如下，其中k是在分支b中出現(xiàn)的擲硬幣步的步數(shù)。定義M接受ω的概率為2022/12/2811概率圖靈機(jī)概率圖靈機(jī)M是一種非確定型圖靈機(jī)，它的每一非確定步BPP類對(duì)于0<=ε<1/2，如果滿足下面的條件則稱M以錯(cuò)誤概率ε識(shí)別語(yǔ)言A。BPP是多項(xiàng)式時(shí)間的概率圖靈機(jī)以錯(cuò)誤概率1/3識(shí)別的語(yǔ)言類。2022/12/2812BPP類對(duì)于0<=ε<1/2，如果滿足下面的條件則稱M以錯(cuò)誤引理10.5引理11.5：設(shè)ε是一個(gè)固定常數(shù)，且0<ε<1/2。又設(shè)M1是一臺(tái)錯(cuò)誤概率為ε的多項(xiàng)式時(shí)間概率圖靈機(jī)，則對(duì)于任意的多項(xiàng)式poly(n)，存在與M1等價(jià)的錯(cuò)誤概率為的多項(xiàng)式時(shí)間概率圖靈機(jī)M2。證明思路：M2用如下方式模擬M1：運(yùn)行M1多項(xiàng)式次，并且取這些運(yùn)行結(jié)果中的多數(shù)作為計(jì)算結(jié)果。錯(cuò)誤概率將隨M1的運(yùn)行次數(shù)指數(shù)下降。2022/12/2813引理10.5引理11.5：設(shè)ε是一個(gè)固定常數(shù)，且0<ε<1/素?cái)?shù)性定理11.6：例子：p通過(guò)在a的費(fèi)馬測(cè)試是指如果一個(gè)數(shù)能通過(guò)所有關(guān)于小于它且與它互素的數(shù)的費(fèi)馬測(cè)試，則稱這個(gè)數(shù)為偽素?cái)?shù)，其中可能包含卡米切爾數(shù)和素?cái)?shù)。2022/12/2814素?cái)?shù)性定理11.6：2022/12/2814測(cè)試偽素?cái)?shù)的多項(xiàng)式概率算法如果p是偽素?cái)?shù)則能通過(guò)全部測(cè)試，如果p不是偽素?cái)?shù)則至多能通過(guò)全部測(cè)試的一半。于是它通過(guò)全部k個(gè)隨機(jī)選擇的測(cè)試的概率不大于，因此該算法以錯(cuò)誤概率識(shí)別所有偽素?cái)?shù)組成的語(yǔ)言。2022/12/2815測(cè)試偽素?cái)?shù)的多項(xiàng)式概率算法如果p是偽素?cái)?shù)則能通過(guò)全部測(cè)試，如避免卡米切爾數(shù)的算法PRIME基本原理是：對(duì)于任意素?cái)?shù)p，1恰好有兩個(gè)模p的平方根：1和-1。而對(duì)于許多合數(shù)，包括卡米切爾數(shù)在內(nèi)，1有4個(gè)或更多的平方根。引理11.7：如果p是一個(gè)奇素?cái)?shù)，則引理11.8：如果p是一個(gè)奇合數(shù)，則2022/12/2816避免卡米切爾數(shù)的算法PRIME基本原理是：對(duì)于任意素?cái)?shù)p，1RP類定理11.9：?jiǎn)蝹?cè)錯(cuò)誤：當(dāng)算法輸出拒絕時(shí)，輸入一定是合數(shù)，當(dāng)輸出接受時(shí)，只能知道輸入可能是素?cái)?shù)。RP是多項(xiàng)式時(shí)間概率圖靈機(jī)識(shí)別的語(yǔ)言類，在這里，在語(yǔ)言中的輸入以不小于1/2的概率被接受；不在語(yǔ)言中的輸入以概率1被拒絕。2022/12/2817RP類定理11.9：2022/12/2817只讀一次的分支程序分支程序是一個(gè)無(wú)圈有向圖，除兩個(gè)輸出頂點(diǎn)標(biāo)記0和1外，其他頂點(diǎn)（詢問(wèn)頂點(diǎn)）都標(biāo)記變量，并引出兩條邊，一條標(biāo)記0、一條標(biāo)記1，在分支程序中指定一個(gè)頂點(diǎn)為起始頂點(diǎn)。只讀一次的分支程序是指在它的從起始頂點(diǎn)到輸出頂點(diǎn)的每一條有向路徑上，每個(gè)變量只能被詢問(wèn)一次。2022/12/2818只讀一次的分支程序分支程序是一個(gè)無(wú)圈有向圖，除兩個(gè)輸出頂點(diǎn)標(biāo)定理10.12多項(xiàng)式時(shí)間概率算法2022/12/2819定理10.122022/12/281910.3交錯(cuò)式2022/12/282010.3交錯(cuò)式2022/12/2820交錯(cuò)式圖靈機(jī)的定義定義：一種特殊的非確定型圖靈機(jī)。除 qaccept和qreject外，它的狀態(tài)分成全 稱狀態(tài)和存在狀態(tài)?！拧摹摹摹摹拧拧ぁぁ?022/12/2821交錯(cuò)式圖靈機(jī)的定義定義：一種特殊的非確定型圖靈機(jī)。除 交錯(cuò)式語(yǔ)言類ATIME(t(n))={L|L是被一臺(tái)O(t(n))時(shí)間的交錯(cuò)式圖靈機(jī)判定的語(yǔ)言}ASPACE(t(n))={L|L是被一臺(tái)O(f(n))空間的交錯(cuò)式圖靈機(jī)判定的語(yǔ)言}2022/12/2822交錯(cuò)式語(yǔ)言類ATIME(t(n))={L|L是被一臺(tái)O(t(例10.16永真式是一個(gè)布爾公式，對(duì)于變量的每一個(gè)賦值，它的值都等于1。令TAUT={<Ф>|Ф是一個(gè)永真式}對(duì)輸入Ф：全稱的選取對(duì)Ф的變量的所有賦值對(duì)一個(gè)具體的賦值，計(jì)算Ф的值如果Ф的值為1，則接受；否則拒絕TAUT∈AP2022/12/2823例10.16永真式是一個(gè)布爾公式，對(duì)于變量的每一個(gè)賦值，它例：令L={<Ф>|Ф不是一個(gè)永真式}對(duì)輸入Ф：存在的選取對(duì)Ф的變量的所有賦值對(duì)一個(gè)具體的賦值，計(jì)算Ф的值如果Ф的值為0，則接受；否則拒絕L∈NPTAUT∈coNP2022/12/2824例：令L={<Ф>|Ф不是一個(gè)永真式}2022/12/28引理10.19對(duì)于f(n)≥n，有 ATIME(f(n))SPACE(f(n))把O(f(n))時(shí)間的交錯(cuò)式圖靈機(jī)M轉(zhuǎn)換成O(f(n))空間的確定型圖靈機(jī)SS如下模擬M：對(duì)于輸入w，S對(duì)M的計(jì)算樹做深度優(yōu)先搜索，確定哪些頂點(diǎn)接受。如果樹根接受，則S接受。2022/12/2825引理10.19對(duì)于f(n)≥n，有2022/12/2825引理10.20對(duì)于f(n)≥n，有 SPACE(f(n))ATIME(f2(n))從O(f(n))空間的確定性圖靈機(jī)M出發(fā)，構(gòu)造一臺(tái)O(f2(n))時(shí)間的交錯(cuò)式圖靈機(jī)S∨∧∧…cmt/2步內(nèi)從c1到cmt/2步內(nèi)從cm到c2t/2步內(nèi)從c1到c2起始格局接受格局2df(n)2022/12/2826引理10.20對(duì)于f(n)≥n，有∨∧∧…cmt/2步內(nèi)從S的每個(gè)分支使用的最大時(shí)間：O(f(n))遞歸深度：log2df(n)=O(f(n))因此，算法在交錯(cuò)時(shí)間O(f2(n))內(nèi)運(yùn)行2022/12/2827S的每個(gè)分支使用的最大時(shí)間：O(f(n))2022/12/2引理10.21對(duì)于對(duì)于f(n)≥logn，有 ASPACE(f(n))TIME(2O(f(n)))構(gòu)造一臺(tái)2O(f(n))時(shí)間的確定型圖靈機(jī)S，模擬O(f(n))空間的交錯(cuò)式圖靈機(jī)。S構(gòu)造M對(duì)w的計(jì)算圖如下：頂點(diǎn)集是M關(guān)于w的所有格局，每一頂點(diǎn)最多使用df(n)空間（d是與M有關(guān)的常數(shù)）。從每一個(gè)格局到M移動(dòng)一步所得到格局連一條邊。2022/12/2828引理10.21對(duì)于對(duì)于f(n)≥logn，有2022/1由于f(n)≥logn，M關(guān)于w的格局?jǐn)?shù)為2O(f(n))。因此，計(jì)算圖的大小為2O(f(n))，可在2O(f(n))時(shí)間內(nèi)構(gòu)造它。掃描時(shí)間類似，且掃描總次數(shù)不超過(guò)頂點(diǎn)數(shù)，所以，使用總時(shí)間為2O(f(n))。2022/12/2829由于f(n)≥logn，M關(guān)于w的格局?jǐn)?shù)為2O(f(n))引理10.22對(duì)于f(n)≥logn，有 ASPACE(f(n))TIME(2O(f(n)))abcd2O(f(n))2O(f(n))qpo2022/12/2830引理10.22對(duì)于f(n)≥logn，有abcd2O(f綜合以上四個(gè)引理，有如下定理定理10.18對(duì)于f(n)≥n，有ATIME(f(n))SPACE(f(n))ATIME(f2(n))對(duì)于f(n)≥logn，有 ASPACE(f(n))=TIME(2O(f(n)))2022/12/2831綜合以上四個(gè)引理，有如下定理2022/12/2831多項(xiàng)式時(shí)間層次定義10.23設(shè)i是大于0的整數(shù)，i交錯(cuò)式圖靈機(jī)是以存在步驟開始，最多含有i此全稱步驟輪換的交錯(cuò)式圖靈機(jī)。i交錯(cuò)式圖靈機(jī)與此類似，只是它以全稱步驟開始。∨∧2022/12/2832多項(xiàng)式時(shí)間層次定義10.23設(shè)i是大于0的整數(shù)，i交錯(cuò)式多項(xiàng)式時(shí)間層次下述語(yǔ)言類集合稱作多項(xiàng)式時(shí)間層次：顯然有：NP=1PcoNP=1P2022/12/2833多項(xiàng)式時(shí)間層次下述語(yǔ)言類集合稱作多項(xiàng)式時(shí)間層次：2022/110.5并行計(jì)算2022/12/283410.5并行計(jì)算2022/12/2834并行計(jì)算機(jī)能夠同時(shí)執(zhí)行多個(gè)操作的計(jì)算機(jī)叫并行計(jì)算機(jī)2022/12/2835并行計(jì)算機(jī)能夠同時(shí)執(zhí)行多個(gè)操作的計(jì)算機(jī)叫并行計(jì)算機(jī)2022/并行計(jì)算模型PRAM模型異步APRAM模型BSP模型logP模型2022/12/2836并行計(jì)算模型PRAM模型2022/12/2836PRAM模型基本概念：由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過(guò)SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。結(jié)構(gòu)圖共享存儲(chǔ)器P1…P2Pn2022/12/2837PRAM模型基本概念：由Fortune和Wyllie1978PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競(jìng)爭(zhēng)、通訊延遲等因素2022/12/2838PRAM模型優(yōu)點(diǎn)2022/12/2838一致布爾電路主要思想：將布爾電路模型用于描述并行計(jì)算優(yōu)點(diǎn)：描述簡(jiǎn)單，證明容易缺點(diǎn)：不靈活，不便于編程2022/12/2839一致布爾電路主要思想：將布爾電路模型用于描述并行計(jì)算2022一致布爾電路門電路：∧∨X1X2X3∨∨2022/12/2840一致布爾電路門電路：∧∨X1X2X3∨∨2022/12/28兩種復(fù)雜度處理器復(fù)雜度：布爾電路的規(guī)模，即布爾電路中門電路的數(shù)目并行時(shí)間復(fù)雜度：輸入變量到輸出門的最長(zhǎng)距離規(guī)模、深度復(fù)雜度：(f(n),g(n))2022/12/2841兩種復(fù)雜度處理器復(fù)雜度：布爾電路的規(guī)模，即布爾電路中門電路的電路族（c1,c2,c3,…,cn）2022/12/2842電路族（c1,c2,c3,…,cn）2022/12/2842例子例10.31：識(shí)別奇數(shù)個(gè)1X1X2X3X4…+++(O(n),O(n))2022/12/2843例子例10.31：識(shí)別奇數(shù)個(gè)1+++(O(n),O(n))2例子例10.31：識(shí)別奇數(shù)個(gè)1X1X2X3X4…+++規(guī)模深度復(fù)雜度(O(n),O(Logn))2022/12/2844例子例10.31：識(shí)別奇數(shù)個(gè)1+++規(guī)模深度復(fù)雜度(O(n)例子例10.32：布爾矩陣乘法（mXm）例11.33：矩陣A（mXm）的傳遞閉包

AVA2V…VAm規(guī)模,深度復(fù)雜度(O(n3/2),O(Logn)),n=2m2規(guī)模,深度復(fù)雜度(O(n5/2),O(Log2n)),n=2m22022/12/2845例子例10.32：布爾矩陣乘法（mXm）規(guī)模,深度復(fù)雜度NC類定義10.34：

i>=1,NCi是能夠用多項(xiàng)式規(guī)模和O(Login)深度的一致布爾電路識(shí)別的語(yǔ)言類；用這種電路族計(jì)算的函數(shù)叫NCi可計(jì)算和NC可計(jì)算的。2022/12/2846NC類定義10.34：2022/12/2846NC類定理10.35：NC1LL是確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語(yǔ)言定理10.36：NLNC2NL是非確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語(yǔ)言定理10.37：NCPP是確定型單帶圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可判定的語(yǔ)言類，P大致對(duì)應(yīng)計(jì)算機(jī)上實(shí)際可解的問(wèn)題類證明：將多項(xiàng)式時(shí)間用于運(yùn)行對(duì)數(shù)空間轉(zhuǎn)換器，生成電路Cn

（對(duì)數(shù)空間可歸約，對(duì)數(shù)空間轉(zhuǎn)換器參見(jiàn)9.16P194）2022/12/2847NC類定理10.35：NC1L2022/12/2847P的完全性定義10.38：B∈P，P中每個(gè)A對(duì)數(shù)空間可歸約到B，則B是P完全的；定理101.40（電路計(jì)算問(wèn)題是否是P完全的）

CIRCUIT-VALUE是P完全的證明：P中任意語(yǔ)言A可對(duì)數(shù)空間歸約到CIRCUIT-VALUE，生成模擬A的電路2022/12/2848P的完全性定義10.38：B∈P，P中每個(gè)A對(duì)數(shù)空間可歸約到10.6：密碼學(xué)報(bào)告人：XXX2022/12/284910.6：密碼學(xué)報(bào)告人：XXX2022/12/2849密碼技術(shù)的起源和發(fā)展1949年，ClaudeShannon在《貝爾系統(tǒng)技術(shù)雜志》上發(fā)表論文《保密系統(tǒng)的通信理論》為單鑰密碼系統(tǒng)奠定了理論基礎(chǔ)。1976年，W.Diffie和M.E.Hellman發(fā)表了《密碼學(xué)的新方向》，建立了公鑰密碼系統(tǒng)，引發(fā)了密碼學(xué)一次革命性的變革。隨著密碼學(xué)理論和技術(shù)的探索和實(shí)踐，人們逐漸認(rèn)識(shí)到認(rèn)證和保密是兩個(gè)獨(dú)立的密碼屬性。G.J.Simmons系統(tǒng)地研究了認(rèn)證問(wèn)題，并建立了一套與香農(nóng)保密理論平行的認(rèn)證理論。2022/12/2850密碼技術(shù)的起源和發(fā)展1949年，ClaudeShannon對(duì)稱密碼（單鑰）對(duì)稱密碼技術(shù)原理對(duì)稱密碼系統(tǒng)加密算法數(shù)據(jù)加密標(biāo)準(zhǔn)DES三重DES國(guó)際數(shù)據(jù)加密算法IDEA高級(jí)加密標(biāo)準(zhǔn)AES2022/12/2851對(duì)稱密碼（單鑰）對(duì)稱密碼技術(shù)原理2022/12/2851密碼安全性密鑰長(zhǎng)度增加：一次性襯墊數(shù)學(xué)上不能證明密碼不可破譯NP完全問(wèn)題規(guī)約到密碼破譯問(wèn)題：平均復(fù)雜度破譯密碼與因式分解對(duì)應(yīng)2022/12/2852密碼安全性密鑰長(zhǎng)度增加：一次性襯墊2022/12/2852公鑰密碼公鑰密碼基本原理：Diffie和Hellman設(shè)想公鑰密碼系統(tǒng)滿足如下條件：通訊雙方A和B容易通過(guò)計(jì)算產(chǎn)生出一對(duì)密鑰（公鑰KU，私鑰KR)在知道公鑰KU和待加密報(bào)文M的情況下，對(duì)于發(fā)送方A，很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)密文C=EKU(M)接受方B使用私鑰容易恢復(fù)原來(lái)的報(bào)文M=DKR(C)=D[EKU(M)]除A、B以外其他人知道公鑰KU,要確定私鑰KR在計(jì)算上式不可行的除A、B以外其他人知道公鑰KU和密文C，要恢復(fù)原來(lái)的明文M在計(jì)算上也是不可行的2022/12/2853公鑰密碼公鑰密碼基本原理：Diffie和Hellman設(shè)想公公鑰密碼系統(tǒng)加密算法密鑰交換RSA算法2022/12/2854公鑰密碼系統(tǒng)加密算法密鑰交換2022/12/2854單向函數(shù)單向函數(shù)滿足下面條件：它將一個(gè)定義閾映射到值域，使得每個(gè)函數(shù)值有一個(gè)唯一的原象；同時(shí)，函數(shù)值容易計(jì)算，而逆計(jì)算不可行。例子11.42(P248)單向函數(shù)構(gòu)造私鑰密碼系統(tǒng)。(P248)2022/12/2855單向函數(shù)單向函數(shù)滿足下面條件：它將一個(gè)定義閾映射到值域，使得天窗函數(shù)天窗函數(shù)（單向陷門函數(shù)）：除非知道某種附加的信息，否則這樣的函數(shù)在一個(gè)方向上容易計(jì)算而在另一個(gè)方向上要計(jì)算不可行。有了附加信息，函數(shù)的逆就可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出來(lái)。例子11.44（P249)天窗函數(shù)構(gòu)造公鑰密碼系統(tǒng)2022/12/2856天窗函數(shù)天窗函數(shù)（單向陷門函數(shù)）：除非知道某種附加的信息，否混沌密碼學(xué)參考文章《混沌保密通信的若干問(wèn)題及混沌加密新方案》?！痘煦缇幋a在信息加密中的應(yīng)用》。2022/12/2857混沌密碼學(xué)參考文章2022/12/2857１０章小結(jié)10.1近似算法、10.2概率算法10.3交錯(cuò)式10.4交互證明，10.5并行計(jì)算10.6密碼學(xué)2022/12/2858１０章小結(jié)10.1近似算法、2022/12/2858AnyQuestion?Thankyou!!!2022/12/2859AnyQuestion?Thankyou!!!202Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可以從下列文件獲得ＰPT素材：

13_10-復(fù)雜理論高級(jí)專題-同學(xué)報(bào)告素材.doc本章提綱10.1近似算法、10.2概率算法10.3交錯(cuò)式10.4交互證明，10.5并行計(jì)算10.6密碼學(xué)2022/12/2860Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可根據(jù)

提供的ＰPT素材+參考以前同學(xué)的報(bào)告，

修改成為有自己見(jiàn)解的討論報(bào)告

建議：

底色用淺色（象牙白，淺黃，白色等）

適合色盲色弱觀眾

字體顏色選擇余地大

在投影機(jī)效果差時(shí)也還能能看見(jiàn)

2022/12/2861Chap10復(fù)雜性理論中的高級(jí)專題(同學(xué)報(bào)告）可近似算法在最優(yōu)化問(wèn)題中，通常試圖在可行解中尋找最好的解，即最優(yōu)解。在實(shí)踐中，可能并不一定非要最優(yōu)解不可，一個(gè)接近最優(yōu)的解可能是足夠好的，而且可能更容易找到。近似算法是為了求近似最優(yōu)解而設(shè)計(jì)的。2022/12/2862近似算法在最優(yōu)化問(wèn)題中，通常試圖在可行解中尋找最好的解，即最頂點(diǎn)覆蓋問(wèn)題若G是無(wú)向圖，則G的頂點(diǎn)覆蓋是節(jié)點(diǎn)的一個(gè)子集，使得G的每條邊都與子集中的節(jié)點(diǎn)之一相關(guān)聯(lián)。2022/12/2863頂點(diǎn)覆蓋問(wèn)題若G是無(wú)向圖，則G的頂點(diǎn)覆蓋是節(jié)點(diǎn)的一個(gè)子集，使最小頂點(diǎn)覆蓋的一個(gè)近似算法下述多項(xiàng)式時(shí)間算法近似地解這個(gè)最優(yōu)化問(wèn)題，它給出一個(gè)頂點(diǎn)覆蓋，其大小不超過(guò)最小頂點(diǎn)覆蓋的大小的2倍。A＝“對(duì)于輸入<G>，這里G是一個(gè)無(wú)向圖：重復(fù)下述操作直至G中所有的邊都與有標(biāo)記的邊相鄰。在G中找一條不與任何有標(biāo)記的邊相鄰的邊。給這條邊作標(biāo)記。輸出所有有標(biāo)記邊的頂點(diǎn)?！?022/12/2864最小頂點(diǎn)覆蓋的一個(gè)近似算法下述多項(xiàng)式時(shí)間算法近似地解這個(gè)最優(yōu)定理1０.1定理11.1：A是一個(gè)多項(xiàng)式時(shí)間算法，它給出G的一個(gè)頂點(diǎn)覆蓋，其大小不超過(guò)最小頂點(diǎn)覆蓋的大小的2倍。證明思路:A的運(yùn)行時(shí)間顯然是多項(xiàng)式界限的。設(shè)X是它輸出的頂點(diǎn)集合，H是有標(biāo)記的邊的集合。因?yàn)镚的每一條邊要么屬于H，要么與H中的一條邊相鄰，因此X與G的所有邊關(guān)聯(lián)，因此X是一個(gè)頂點(diǎn)覆蓋。證明X的大小不超過(guò)最小頂點(diǎn)覆蓋Y的大小的2倍。X的大小是H的2倍H不大于Y2022/12/2865定理1０.1定理11.1：A是一個(gè)多項(xiàng)式時(shí)間算法，它給出G的k-優(yōu)算法如果一個(gè)最小化問(wèn)題的近似算法總能找到不超過(guò)最優(yōu)解k倍的可行解，則稱這個(gè)算法是k-優(yōu)的。對(duì)于最大化問(wèn)題，一個(gè)k-優(yōu)近似算法總能找到不小于最優(yōu)解大小的1/k的可行解。2022/12/2866k-優(yōu)算法如果一個(gè)最小化問(wèn)題的近似算法總能找到不超過(guò)最優(yōu)解k最大割集的近似算法把頂點(diǎn)集V劃分成兩個(gè)不相交的子集S和T，稱為無(wú)向圖中的割。頂點(diǎn)分別在兩個(gè)子集中的邊稱為割邊，割邊的數(shù)目稱為割的大小。B＝“對(duì)于輸入<G>，這里G是頂點(diǎn)集為V的無(wú)向圖：令S＝?和T＝V。如果把一個(gè)頂點(diǎn)從S移到T或者從T移到S，使割的大小變大，則做這樣的移動(dòng)，并且重復(fù)這一步。如果不存在這樣的頂點(diǎn)，則輸出當(dāng)前的割并且停止?！?022/12/2867最大割集的近似算法把頂點(diǎn)集V劃分成兩個(gè)不相交的子集S和T，稱定理1０.2定理11.2：B是最大割集的2-優(yōu)的多項(xiàng)式近似算法。證明：割的大小不超過(guò)G的邊數(shù)，故B是多項(xiàng)式時(shí)間的。證明B輸出的割X至少包含G中的所有邊的一半。X的每個(gè)頂點(diǎn)的割邊>=非割邊。X的所有頂點(diǎn)的割邊數(shù)和＝X的割邊總數(shù)×2。X的所有頂點(diǎn)的非割邊數(shù)和＝X的非割邊總數(shù)×2。X的割邊數(shù)和>=X的非割邊數(shù)和X的割邊數(shù)>=G的所有邊數(shù)/2

G的所有邊數(shù)>=最大割邊數(shù)2022/12/2868定理1０.2定理11.2：B是最大割集的2-優(yōu)的多項(xiàng)式近似算概率算法概率算法使用隨機(jī)過(guò)程的結(jié)果。典型包含一條“扔硬幣”的指令，并且扔硬幣的結(jié)果可能影響算法后面的執(zhí)行和輸出。BPP類素?cái)?shù)性只讀一次的分支程序2022/12/2869概率算法概率算法使用隨機(jī)過(guò)程的結(jié)果。典型包含一條“扔硬幣”的概率圖靈機(jī)概率圖靈機(jī)M是一種非確定型圖靈機(jī)，它的每一非確定步，稱作擲硬幣步，并且有兩個(gè)合法的下次動(dòng)作。定義分支b的概率如下，其中k是在分支b中出現(xiàn)的擲硬幣步的步數(shù)。定義M接受ω的概率為2022/12/2870概率圖靈機(jī)概率圖靈機(jī)M是一種非確定型圖靈機(jī)，它的每一非確定步BPP類對(duì)于0<=ε<1/2，如果滿足下面的條件則稱M以錯(cuò)誤概率ε識(shí)別語(yǔ)言A。BPP是多項(xiàng)式時(shí)間的概率圖靈機(jī)以錯(cuò)誤概率1/3識(shí)別的語(yǔ)言類。2022/12/2871BPP類對(duì)于0<=ε<1/2，如果滿足下面的條件則稱M以錯(cuò)誤引理10.5引理11.5：設(shè)ε是一個(gè)固定常數(shù)，且0<ε<1/2。又設(shè)M1是一臺(tái)錯(cuò)誤概率為ε的多項(xiàng)式時(shí)間概率圖靈機(jī)，則對(duì)于任意的多項(xiàng)式poly(n)，存在與M1等價(jià)的錯(cuò)誤概率為的多項(xiàng)式時(shí)間概率圖靈機(jī)M2。證明思路：M2用如下方式模擬M1：運(yùn)行M1多項(xiàng)式次，并且取這些運(yùn)行結(jié)果中的多數(shù)作為計(jì)算結(jié)果。錯(cuò)誤概率將隨M1的運(yùn)行次數(shù)指數(shù)下降。2022/12/2872引理10.5引理11.5：設(shè)ε是一個(gè)固定常數(shù)，且0<ε<1/素?cái)?shù)性定理11.6：例子：p通過(guò)在a的費(fèi)馬測(cè)試是指如果一個(gè)數(shù)能通過(guò)所有關(guān)于小于它且與它互素的數(shù)的費(fèi)馬測(cè)試，則稱這個(gè)數(shù)為偽素?cái)?shù)，其中可能包含卡米切爾數(shù)和素?cái)?shù)。2022/12/2873素?cái)?shù)性定理11.6：2022/12/2814測(cè)試偽素?cái)?shù)的多項(xiàng)式概率算法如果p是偽素?cái)?shù)則能通過(guò)全部測(cè)試，如果p不是偽素?cái)?shù)則至多能通過(guò)全部測(cè)試的一半。于是它通過(guò)全部k個(gè)隨機(jī)選擇的測(cè)試的概率不大于，因此該算法以錯(cuò)誤概率識(shí)別所有偽素?cái)?shù)組成的語(yǔ)言。2022/12/2874測(cè)試偽素?cái)?shù)的多項(xiàng)式概率算法如果p是偽素?cái)?shù)則能通過(guò)全部測(cè)試，如避免卡米切爾數(shù)的算法PRIME基本原理是：對(duì)于任意素?cái)?shù)p，1恰好有兩個(gè)模p的平方根：1和-1。而對(duì)于許多合數(shù)，包括卡米切爾數(shù)在內(nèi)，1有4個(gè)或更多的平方根。引理11.7：如果p是一個(gè)奇素?cái)?shù)，則引理11.8：如果p是一個(gè)奇合數(shù)，則2022/12/2875避免卡米切爾數(shù)的算法PRIME基本原理是：對(duì)于任意素?cái)?shù)p，1RP類定理11.9：?jiǎn)蝹?cè)錯(cuò)誤：當(dāng)算法輸出拒絕時(shí)，輸入一定是合數(shù)，當(dāng)輸出接受時(shí)，只能知道輸入可能是素?cái)?shù)。RP是多項(xiàng)式時(shí)間概率圖靈機(jī)識(shí)別的語(yǔ)言類，在這里，在語(yǔ)言中的輸入以不小于1/2的概率被接受；不在語(yǔ)言中的輸入以概率1被拒絕。2022/12/2876RP類定理11.9：2022/12/2817只讀一次的分支程序分支程序是一個(gè)無(wú)圈有向圖，除兩個(gè)輸出頂點(diǎn)標(biāo)記0和1外，其他頂點(diǎn)（詢問(wèn)頂點(diǎn)）都標(biāo)記變量，并引出兩條邊，一條標(biāo)記0、一條標(biāo)記1，在分支程序中指定一個(gè)頂點(diǎn)為起始頂點(diǎn)。只讀一次的分支程序是指在它的從起始頂點(diǎn)到輸出頂點(diǎn)的每一條有向路徑上，每個(gè)變量只能被詢問(wèn)一次。2022/12/2877只讀一次的分支程序分支程序是一個(gè)無(wú)圈有向圖，除兩個(gè)輸出頂點(diǎn)標(biāo)定理10.12多項(xiàng)式時(shí)間概率算法2022/12/2878定理10.122022/12/281910.3交錯(cuò)式2022/12/287910.3交錯(cuò)式2022/12/2820交錯(cuò)式圖靈機(jī)的定義定義：一種特殊的非確定型圖靈機(jī)。除 qaccept和qreject外，它的狀態(tài)分成全 稱狀態(tài)和存在狀態(tài)?！拧摹摹摹摹拧拧ぁぁ?022/12/2880交錯(cuò)式圖靈機(jī)的定義定義：一種特殊的非確定型圖靈機(jī)。除 交錯(cuò)式語(yǔ)言類ATIME(t(n))={L|L是被一臺(tái)O(t(n))時(shí)間的交錯(cuò)式圖靈機(jī)判定的語(yǔ)言}ASPACE(t(n))={L|L是被一臺(tái)O(f(n))空間的交錯(cuò)式圖靈機(jī)判定的語(yǔ)言}2022/12/2881交錯(cuò)式語(yǔ)言類ATIME(t(n))={L|L是被一臺(tái)O(t(例10.16永真式是一個(gè)布爾公式，對(duì)于變量的每一個(gè)賦值，它的值都等于1。令TAUT={<Ф>|Ф是一個(gè)永真式}對(duì)輸入Ф：全稱的選取對(duì)Ф的變量的所有賦值對(duì)一個(gè)具體的賦值，計(jì)算Ф的值如果Ф的值為1，則接受；否則拒絕TAUT∈AP2022/12/2882例10.16永真式是一個(gè)布爾公式，對(duì)于變量的每一個(gè)賦值，它例：令L={<Ф>|Ф不是一個(gè)永真式}對(duì)輸入Ф：存在的選取對(duì)Ф的變量的所有賦值對(duì)一個(gè)具體的賦值，計(jì)算Ф的值如果Ф的值為0，則接受；否則拒絕L∈NPTAUT∈coNP2022/12/2883例：令L={<Ф>|Ф不是一個(gè)永真式}2022/12/28引理10.19對(duì)于f(n)≥n，有 ATIME(f(n))SPACE(f(n))把O(f(n))時(shí)間的交錯(cuò)式圖靈機(jī)M轉(zhuǎn)換成O(f(n))空間的確定型圖靈機(jī)SS如下模擬M：對(duì)于輸入w，S對(duì)M的計(jì)算樹做深度優(yōu)先搜索，確定哪些頂點(diǎn)接受。如果樹根接受，則S接受。2022/12/2884引理10.19對(duì)于f(n)≥n，有2022/12/2825引理10.20對(duì)于f(n)≥n，有 SPACE(f(n))ATIME(f2(n))從O(f(n))空間的確定性圖靈機(jī)M出發(fā)，構(gòu)造一臺(tái)O(f2(n))時(shí)間的交錯(cuò)式圖靈機(jī)S∨∧∧…cmt/2步內(nèi)從c1到cmt/2步內(nèi)從cm到c2t/2步內(nèi)從c1到c2起始格局接受格局2df(n)2022/12/2885引理10.20對(duì)于f(n)≥n，有∨∧∧…cmt/2步內(nèi)從S的每個(gè)分支使用的最大時(shí)間：O(f(n))遞歸深度：log2df(n)=O(f(n))因此，算法在交錯(cuò)時(shí)間O(f2(n))內(nèi)運(yùn)行2022/12/2886S的每個(gè)分支使用的最大時(shí)間：O(f(n))2022/12/2引理10.21對(duì)于對(duì)于f(n)≥logn，有 ASPACE(f(n))TIME(2O(f(n)))構(gòu)造一臺(tái)2O(f(n))時(shí)間的確定型圖靈機(jī)S，模擬O(f(n))空間的交錯(cuò)式圖靈機(jī)。S構(gòu)造M對(duì)w的計(jì)算圖如下：頂點(diǎn)集是M關(guān)于w的所有格局，每一頂點(diǎn)最多使用df(n)空間（d是與M有關(guān)的常數(shù)）。從每一個(gè)格局到M移動(dòng)一步所得到格局連一條邊。2022/12/2887引理10.21對(duì)于對(duì)于f(n)≥logn，有2022/1由于f(n)≥logn，M關(guān)于w的格局?jǐn)?shù)為2O(f(n))。因此，計(jì)算圖的大小為2O(f(n))，可在2O(f(n))時(shí)間內(nèi)構(gòu)造它。掃描時(shí)間類似，且掃描總次數(shù)不超過(guò)頂點(diǎn)數(shù)，所以，使用總時(shí)間為2O(f(n))。2022/12/2888由于f(n)≥logn，M關(guān)于w的格局?jǐn)?shù)為2O(f(n))引理10.22對(duì)于f(n)≥logn，有 ASPACE(f(n))TIME(2O(f(n)))abcd2O(f(n))2O(f(n))qpo2022/12/2889引理10.22對(duì)于f(n)≥logn，有abcd2O(f綜合以上四個(gè)引理，有如下定理定理10.18對(duì)于f(n)≥n，有ATIME(f(n))SPACE(f(n))ATIME(f2(n))對(duì)于f(n)≥logn，有 ASPACE(f(n))=TIME(2O(f(n)))2022/12/2890綜合以上四個(gè)引理，有如下定理2022/12/2831多項(xiàng)式時(shí)間層次定義10.23設(shè)i是大于0的整數(shù)，i交錯(cuò)式圖靈機(jī)是以存在步驟開始，最多含有i此全稱步驟輪換的交錯(cuò)式圖靈機(jī)。i交錯(cuò)式圖靈機(jī)與此類似，只是它以全稱步驟開始?！拧?022/12/2891多項(xiàng)式時(shí)間層次定義10.23設(shè)i是大于0的整數(shù)，i交錯(cuò)式多項(xiàng)式時(shí)間層次下述語(yǔ)言類集合稱作多項(xiàng)式時(shí)間層次：顯然有：NP=1PcoNP=1P2022/12/2892多項(xiàng)式時(shí)間層次下述語(yǔ)言類集合稱作多項(xiàng)式時(shí)間層次：2022/110.5并行計(jì)算2022/12/289310.5并行計(jì)算2022/12/2834并行計(jì)算機(jī)能夠同時(shí)執(zhí)行多個(gè)操作的計(jì)算機(jī)叫并行計(jì)算機(jī)2022/12/2894并行計(jì)算機(jī)能夠同時(shí)執(zhí)行多個(gè)操作的計(jì)算機(jī)叫并行計(jì)算機(jī)2022/并行計(jì)算模型PRAM模型異步APRAM模型BSP模型logP模型2022/12/2895并行計(jì)算模型PRAM模型2022/12/2836PRAM模型基本概念：由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過(guò)SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。結(jié)構(gòu)圖共享存儲(chǔ)器P1…P2Pn2022/12/2896PRAM模型基本概念：由Fortune和Wyllie1978PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競(jìng)爭(zhēng)、通訊延遲等因素2022/12/2897PRAM模型優(yōu)點(diǎn)2022/12/2838一致布爾電路主要思想：將布爾電路模型用于描述并行計(jì)算優(yōu)點(diǎn)：描述簡(jiǎn)單，證明容易缺點(diǎn)：不靈活，不便于編程2022/12/2898一致布爾電路主要思想：將布爾電路模型用于描述并行計(jì)算2022一致布爾電路門電路：∧∨X1X2X3∨∨2022/12/2899一致布爾電路門電路：∧∨X1X2X3∨∨2022/12/28兩種復(fù)雜度處理器復(fù)雜度：布爾電路的規(guī)模，即布爾電路中門電路的數(shù)目并行時(shí)間復(fù)雜度：輸入變量到輸出門的最長(zhǎng)距離規(guī)模、深度復(fù)雜度：(f(n),g(n))2022/12/28100兩種復(fù)雜度處理器復(fù)雜度：布爾電路的規(guī)模，即布爾電路中門電路的電路族（c1,c2,c3,…,cn）2022/12/28101電路族（c1,c2,c3,…,cn）2022/12/2842例子例10.31：識(shí)別奇數(shù)個(gè)1X1X2X3X4…+++(O(n),O(n))2022/12/28102例子例10.31：識(shí)別奇數(shù)個(gè)1+++(O(n),O(n))2例子例10.31：識(shí)別奇數(shù)個(gè)1X1X2X3X4…+++規(guī)模深度復(fù)雜度(O(n),O(Logn))2022/12/28103例子例10.31：識(shí)別奇數(shù)個(gè)1+++規(guī)模深度復(fù)雜度(O(n)例子例10.32：布爾矩陣乘法（mXm）例11.33：矩陣A（mXm）的傳遞閉包

AVA2V…VAm規(guī)模,深度復(fù)雜度(O(n3/2),O(Logn)),n=2m2規(guī)模,深度復(fù)雜度(O(n5/2),O(Log2n)),n=2m22022/12/28104例子例10.32：布爾矩陣乘法（mXm）規(guī)模,深度復(fù)雜度NC類定義10.34：

i>=1,NCi是能夠用多項(xiàng)式規(guī)模和O(Login)深度的一致布爾電路識(shí)別的語(yǔ)言類；用這種電路族計(jì)算的函數(shù)叫NCi可計(jì)算和NC可計(jì)算的。2022/12/28105NC類定義10.34：2022/12/2846NC類定理10.35：NC1LL是確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語(yǔ)言定理10.36：NLNC2NL是非確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語(yǔ)言定理10.37：NCPP是確定型單帶圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可判定的語(yǔ)言類，P大致對(duì)應(yīng)計(jì)算機(jī)上實(shí)際可解的問(wèn)題類證明：將多項(xiàng)式時(shí)間用于運(yùn)行對(duì)數(shù)空間轉(zhuǎn)換器，生成電路Cn

（對(duì)數(shù)空間可歸約，對(duì)數(shù)空間轉(zhuǎn)換器參見(jiàn)9.