密碼學(xué)的計(jì)算復(fù)雜性理論幽默來(lái)自智慧，惡語(yǔ)來(lái)自無(wú)能密碼學(xué)的計(jì)算復(fù)雜性理論幽默來(lái)自智慧，惡語(yǔ)來(lái)自無(wú)能1口密碼學(xué)的計(jì)算復(fù)雜性理論口密碼學(xué)的計(jì)算復(fù)雜性理論2算法與算法復(fù)雜性口算法:求解某個(gè)問(wèn)題的一系列具體步驟,可能一個(gè)問(wèn)題有多種算法理解為求解該問(wèn)題的計(jì)算機(jī)程序)?？诳山馀c不可解:如果一個(gè)算法能解決該問(wèn)題的所有實(shí)例,則稱該算法能解答該問(wèn)題。如果針對(duì)一個(gè)問(wèn)題至少存在個(gè)算法可以解答該問(wèn)題,則稱該問(wèn)題是可解的。否則稱為該問(wèn)題是不可解的。算法與算法復(fù)雜性3口算法的復(fù)雜性個(gè)算法的復(fù)雜性是由該算法所需要的最大運(yùn)算時(shí)間和存儲(chǔ)空間來(lái)度量的。它們分別是規(guī)模為n(輸入數(shù)據(jù)的長(zhǎng)度)的所有實(shí)例的時(shí)間和空間需求的平均值的函數(shù)7(n)和S(n)個(gè)算法的復(fù)雜性通常用符號(hào)“O”表示量級(jí)。好處在于它與處理系統(tǒng)無(wú)關(guān)(如:處理機(jī)速度、數(shù)據(jù)類型及表示)。f(m)=O(g(n)表示存在常數(shù)c和n,對(duì)所有n≥nf(n)≤cl(m)則稱函數(shù)f(m)當(dāng)n充分大時(shí)上有界,且g(是它的一個(gè)上界,記為f(n)=0(g(n))。即f(m)的階不高于g(n)的階?？谒惴ǖ膹?fù)雜性4口算法按復(fù)雜性分類多項(xiàng)式時(shí)間算法時(shí)間復(fù)雜性為O(n),k為常數(shù)。指數(shù)時(shí)間算法時(shí)間復(fù)雜性為O(),t為常數(shù),h(n)是多項(xiàng)式。當(dāng)h(n)大于常數(shù)小于線性函數(shù)時(shí),稱為超多項(xiàng)式時(shí)間算法口算法按復(fù)雜性分類5例如:Hanoi塔問(wèn)題算法的時(shí)間復(fù)雜度,可以用一個(gè)指數(shù)函數(shù)O(2)來(lái)表示,顯然,當(dāng)n很大(如10000時(shí),計(jì)算機(jī)是無(wú)法處理的。相反,當(dāng)算法的時(shí)間復(fù)雜度的表示函數(shù)是一個(gè)多項(xiàng)式,如O(n2)時(shí),則可以處理。因此,一個(gè)問(wèn)題求解算法的時(shí)間復(fù)雜度大于多項(xiàng)式(如指數(shù)函數(shù))時(shí),算法的執(zhí)行時(shí)間將隨n的增加而急劇增長(zhǎng),以致即使是中等規(guī)模的問(wèn)題也不能求解出來(lái),于是在計(jì)算復(fù)雜性中,將這一類問(wèn)題稱為難解性問(wèn)題。人工智能領(lǐng)域中的狀態(tài)圖搜索問(wèn)題(解空間的表示或狀態(tài)空間搜索問(wèn)題)就是一類典型的難解性問(wèn)題。64個(gè)盤子例如:Hanoi塔問(wèn)題算法的時(shí)間復(fù)雜度,可以用一個(gè)指數(shù)函數(shù)6NP問(wèn)題與計(jì)算復(fù)雜性理論理自機(jī)←—m計(jì)算機(jī),并明究模型的性質(zhì)一論就的性可單現(xiàn)想計(jì)算機(jī)中,研究什論算mn可解的問(wèn)題在實(shí)際計(jì)算機(jī)上理復(fù)么計(jì)算的資源消耗情況并根據(jù)一~論雜消耗情況對(duì)問(wèn)題進(jìn)行分類性NP問(wèn)題與計(jì)算復(fù)雜性理論7口圖靈機(jī)模型讀寫頭狀態(tài)控制器圖靈在1936年提出了著名的圖靈機(jī)模型(計(jì)算模型):n圖靈機(jī)由一個(gè)無(wú)限長(zhǎng)的帶子(被劃分成均勻的方格)、一個(gè)磁帶讀/寫頭和一個(gè)有限狀態(tài)控制器組成。在每一步計(jì)算中,圖靈機(jī)從磁帶上讀出一個(gè)符號(hào),并由有限狀態(tài)控制器決定是否在當(dāng)前的磁帶區(qū)上寫入不同的符號(hào),然后決定是否需要將磁帶讀/寫頭向前或向后移動(dòng)一位。當(dāng)前的計(jì)算機(jī),在理論上都是可以被圖靈機(jī)模擬的,其原理和圖靈機(jī)是相同的,甚至還包含了存儲(chǔ)程序的思想口圖靈機(jī)模型8口確定的圖靈機(jī):有無(wú)限讀寫能力的有限自動(dòng)機(jī),每一步操作的結(jié)果唯一確定口非確定的圖靈機(jī):有無(wú)限讀寫能力的有限自動(dòng)機(jī),每一步操作的結(jié)果有多種選擇口易解問(wèn)題與難解問(wèn)題:在確定圖靈機(jī)上用多項(xiàng)式時(shí)間可解的問(wèn)題,稱為全體易解問(wèn)題集合記為P。否則,稱為難解問(wèn)題。在計(jì)算復(fù)雜性理論中,將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題稱為P問(wèn)題,而將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問(wèn)題稱為NP問(wèn)題。由于P類問(wèn)題采用的是確定性算法,NP類問(wèn)題釆用的是非確定性算法,而確定性算法是非確定性算法的一種特例,因此,可以斷定PcNP。口確定的圖靈機(jī):有無(wú)限讀寫能力的有限自動(dòng)機(jī),每9或者說(shuō):在非確定的圖靈機(jī)上用多項(xiàng)式時(shí)間可解的問(wèn)題,稱為非確定型多項(xiàng)式時(shí)間可解問(wèn)題,即NP問(wèn)題。其含義是若機(jī)器猜測(cè)一個(gè)解,非確定的圖靈機(jī)就可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證它的正確性。(即:可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證某個(gè)解是否合法的問(wèn)題)全體非確定型多項(xiàng)式時(shí)間可解類記作NP類。NP難問(wèn)題:如果對(duì)于某個(gè)問(wèn)題X,任意NP問(wèn)題Y,可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)換為(歸約)到ⅹ。通俗地講X至少和Y一樣難,則稱X是NP難的問(wèn)題?；蛘哒f(shuō):10從前,有一個(gè)酷愛數(shù)學(xué)的年輕國(guó)王向鄰國(guó)一位聰明美麗的公主求婚。公主出了這樣一道題:求出48770428433377171的一個(gè)真因子。若國(guó)王能在一天之內(nèi)求出答案,公主便接受他的求婚。國(guó)王回去后立即開始逐個(gè)數(shù)地進(jìn)行計(jì)算,他從早到晩,共算了三萬(wàn)多個(gè)數(shù),最終還是沒有結(jié)果。國(guó)王向公主求情,公主將答案相告:223092827是它的一個(gè)真因子。國(guó)王很快就驗(yàn)證了這個(gè)數(shù)確能除盡48770428433377171。公主說(shuō):“我再給你一次機(jī)會(huì),如果還求不出,將來(lái)你只好做我的證婚人了?！眹?guó)王立即回國(guó),并向時(shí)任宰相的大數(shù)學(xué)家求教,大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為17位,則最小的一個(gè)真因子不會(huì)超過(guò)9位,于是他給國(guó)王出了一個(gè)主意:按自然數(shù)的順序給全國(guó)的老百姓每人編一個(gè)號(hào)發(fā)下去,等公主給出數(shù)目后,立即將它們通報(bào)全國(guó),讓每個(gè)老百姓用自己的編號(hào)去除這個(gè)數(shù),除盡了立即上報(bào),賞金萬(wàn)兩。最后,國(guó)王用這個(gè)辦法求婚成功。返回從前,有一個(gè)酷愛數(shù)學(xué)的年輕國(guó)王向鄰國(guó)一位聰明美麗11密碼學(xué)的計(jì)算復(fù)雜性理論課件12密碼學(xué)的計(jì)算復(fù)雜性理論課件13密碼學(xué)的計(jì)算復(fù)雜性理論課件14密碼學(xué)的計(jì)算復(fù)雜性理論課件15密碼學(xué)的計(jì)算復(fù)雜性理論課件16密碼學(xué)的計(jì)算復(fù)雜性理論課件17密碼學(xué)的計(jì)算復(fù)雜性理論課件18密碼學(xué)的計(jì)算復(fù)雜性理論課件19密碼學(xué)的計(jì)算復(fù)雜性理論課件20密碼學(xué)的計(jì)算復(fù)雜性理論課件21密碼學(xué)的計(jì)算復(fù)雜性理論課件22密碼學(xué)的計(jì)算復(fù)雜性理論課件23密碼學(xué)的計(jì)算復(fù)雜性理論課件24密碼學(xué)的計(jì)算復(fù)雜性理論課件25密碼學(xué)的計(jì)算復(fù)雜性理論課件26密碼學(xué)的計(jì)算復(fù)雜性理論課件27密碼學(xué)的計(jì)算復(fù)雜性理論課件28密碼學(xué)的計(jì)算復(fù)雜性理論課件29密碼學(xué)的計(jì)算復(fù)雜性理論課件30密碼學(xué)的計(jì)算復(fù)雜性理論課件31密碼學(xué)的計(jì)算復(fù)雜性理論課件32密碼學(xué)的計(jì)算復(fù)雜性理論課件33密碼學(xué)的計(jì)算復(fù)雜性理論課件34密碼學(xué)的計(jì)算復(fù)雜性理論課件35密碼學(xué)的計(jì)算復(fù)雜性理論課件36密碼學(xué)的計(jì)算復(fù)雜性理論課件3731、只有永遠(yuǎn)躺在泥坑里的人，才不會(huì)再掉進(jìn)坑里?！诟駹?/p>

32、希望的燈一旦熄滅，生活剎那間