計(jì)算復(fù)雜性理論

信息安全數(shù)學(xué)2017.2北京工業(yè)大學(xué)信息學(xué)部課程簡介為了解決信息通信系統(tǒng)信息的非授權(quán)訪問，密碼技術(shù)被廣泛的用于通信系統(tǒng)的各個(gè)層面?，F(xiàn)代密碼技術(shù)是以數(shù)學(xué)為基礎(chǔ)發(fā)展起來的，其中數(shù)論和代數(shù)結(jié)構(gòu)是解決現(xiàn)代密碼關(guān)鍵技術(shù)的理論基礎(chǔ)。而現(xiàn)有各學(xué)科教學(xué)體制中缺乏專門介紹密碼以及信息安全所涉及的數(shù)學(xué)知識(shí)的課程。因此，為了適應(yīng)信息技術(shù)發(fā)展的需求，將信息安全相關(guān)的數(shù)學(xué)作為一門獨(dú)立的基礎(chǔ)課程，為解決信息安全理論與實(shí)踐問題提供數(shù)學(xué)基礎(chǔ)。課程地位本課程為信息安全專業(yè)以及與通信相關(guān)的各專業(yè)的本科生奠定一定的數(shù)學(xué)基礎(chǔ)，提高他們認(rèn)識(shí)、分析和解決信息安全問題的能力。本課程是學(xué)科基礎(chǔ)課，系統(tǒng)的介紹與信息安全理論與技術(shù)相關(guān)的數(shù)學(xué)知識(shí)以及一些常用的計(jì)算方法，并通過一些應(yīng)用實(shí)例使學(xué)生了解數(shù)學(xué)知識(shí)在信息安全中的應(yīng)用，同時(shí)通過這些實(shí)例幫助學(xué)生更好的理解抽象的數(shù)學(xué)知識(shí)，為進(jìn)一步應(yīng)用數(shù)學(xué)知識(shí)解決信息安全領(lǐng)域的理論與實(shí)踐問題奠定扎實(shí)的數(shù)學(xué)基礎(chǔ)。緒論信息系統(tǒng)安全包含以下四個(gè)方面：設(shè)安備全：設(shè)備的穩(wěn)定性、可靠性、可用性數(shù)據(jù)安全：數(shù)據(jù)的秘密性、完整性、可用性內(nèi)容安全：信息內(nèi)容在政治上是健康的，符合國家法律法規(guī)、符合中華民族優(yōu)良的道德規(guī)范行為安全：行為的秘密性、行為的完整性、行為的可控性（以確保信息安全）信息安全的內(nèi)涵信息系統(tǒng)的硬件系統(tǒng)安全和操作系統(tǒng)安全是信息系統(tǒng)安全的基礎(chǔ)，密碼和網(wǎng)絡(luò)安全等技術(shù)是信息系統(tǒng)安全的關(guān)鍵技術(shù)。為了表述簡單直接將信息系統(tǒng)安全簡稱為信息安全。信息安全學(xué)科是研究信息獲取、信息存儲(chǔ)、信息傳輸和信息處理中的信息安全保障問題的一門新興學(xué)科。信息安全學(xué)科的性質(zhì)信息安全學(xué)科是綜合計(jì)算機(jī)、通信、電子、數(shù)學(xué)、物理、生物、管理、法律和教育等學(xué)科，并發(fā)展演繹而形成的交叉學(xué)科。信息安全學(xué)科已經(jīng)獨(dú)立，并形成了自己的理論、技術(shù)和應(yīng)用，正服務(wù)于信息社會(huì)。信息安全的主要研究方向密碼學(xué)網(wǎng)絡(luò)安全信息系統(tǒng)安全信息內(nèi)容安全信息對(duì)抗信息安全的理論基礎(chǔ)數(shù)學(xué)密碼學(xué)——代數(shù)、數(shù)論、概率統(tǒng)計(jì)。安全協(xié)議——邏輯學(xué)信息對(duì)抗——博弈論信息論、控制論和系統(tǒng)論計(jì)算理論：可計(jì)算理論和計(jì)算復(fù)雜性理論主要內(nèi)容及時(shí)間安排計(jì)算復(fù)雜性（6課時(shí)）因式分解困難問題及其所涉及的數(shù)論基礎(chǔ)（28課時(shí)）離散對(duì)數(shù)問題及其現(xiàn)代數(shù)學(xué)基礎(chǔ)（10課時(shí)）邏輯學(xué)基礎(chǔ)（6課時(shí)）量子力學(xué)基礎(chǔ)（2課時(shí)）總復(fù)習(xí)（2課時(shí)）閉卷考試：平時(shí)20%+試卷80%答疑：每周三下午2-4點(diǎn)，信西404A。第一講：計(jì)算復(fù)雜性計(jì)算復(fù)雜性的概念計(jì)算量的表示算法與計(jì)算量計(jì)算復(fù)雜性影響計(jì)算復(fù)雜性的因素計(jì)算復(fù)雜性的概念（1）

計(jì)算復(fù)雜性理論（Computationalcomplexitytheory）是計(jì)算理論的一部分，研究計(jì)算問題時(shí)所需的資源，比如時(shí)間和空間，以及如何盡可能的節(jié)省這些資源。

計(jì)算復(fù)雜性理論所研究的資源中最常見的是時(shí)間（要通過多少步才能解決問題）和空間（在解決問題時(shí)需要多少內(nèi)存）。其他資源亦可考慮，例如在并行計(jì)算中，需要多少并行處理器才能解決問題。計(jì)算復(fù)雜性的概念（2）時(shí)間復(fù)雜度是指在計(jì)算機(jī)科學(xué)與工程領(lǐng)域完成一個(gè)算法所需要的時(shí)間，是衡量一個(gè)算法優(yōu)劣的重要參數(shù)。時(shí)間復(fù)雜度越小，說明該算法效率越高，則該算法越有價(jià)值?？臻g復(fù)雜度是指計(jì)算機(jī)科學(xué)領(lǐng)域完成一個(gè)算法所需要占用的存儲(chǔ)空間，一般是輸入?yún)?shù)的函數(shù)。它是算法優(yōu)劣的重要度量指標(biāo)，一般來說，空間復(fù)雜度越小，算法越好。我們假設(shè)有一個(gè)圖靈機(jī)來解決某一類語言的某一問題，設(shè)有X個(gè)字（word）屬于這個(gè)問題，把X放入這個(gè)圖靈機(jī)的輸入端，這個(gè)圖靈機(jī)為解決此問題所需要的工作帶格子數(shù)總和稱為空間。計(jì)算復(fù)雜性的概念（3）復(fù)雜度理論和可計(jì)算性理論不同，可計(jì)算性理論的重心在于問題能否解決，不管需要多少資源。而復(fù)雜性理論作為計(jì)算理論的分支，某種程度上被認(rèn)為和算法理論是一種“矛”與“盾”的關(guān)系，即算法理論專注于設(shè)計(jì)有效的算法，而復(fù)雜性理論專注于理解為什么對(duì)于某類問題，不存在有效的算法。歷史回顧在20世紀(jì)50年代，Trahtenbrot和Rabin的論文被認(rèn)為是該領(lǐng)域最早的文獻(xiàn)。而一般說來，被公認(rèn)為奠定了計(jì)算復(fù)雜性領(lǐng)域基礎(chǔ)的是Hartmanis和Stearns的1960年代的論文Onthecomputationalcomplexityofalgorithms。在這篇論文中，作者引入了時(shí)間復(fù)雜性類TIME(f(n))的概念，并利用對(duì)角線法證明了時(shí)間層級(jí)定理（TimeHierarchyTheorem）。在此之后，許多研究者對(duì)復(fù)雜性理論作出了貢獻(xiàn)。期間重要的發(fā)現(xiàn)包括：對(duì)隨機(jī)算法的去隨機(jī)化（derandomization）的研究，對(duì)近似算法的不可近似性（hardnessofapproximation）的研究，以及交互式證明系統(tǒng)（Interactiveproofsystem）理論和零知識(shí)證明（Zero-knowledgeproof）等。特別的復(fù)雜性理論對(duì)近代密碼學(xué)的影響非常顯著，而最近，復(fù)雜性理論的研究者又進(jìn)入了博弈論領(lǐng)域，并創(chuàng)立了“算法博弈論”（algorithmicgametheory）這一分支。計(jì)算模型和計(jì)算資源計(jì)算復(fù)雜性理論的研究對(duì)象是算法在執(zhí)行時(shí)所需的計(jì)算資源，而為了討論這一點(diǎn)，我們必須假設(shè)算法是在某個(gè)計(jì)算模型上運(yùn)行的。常討論的計(jì)算模型包括圖靈機(jī)（Turingmachine）和電路（circuit），它們分別是一致性（uniform）和非一致性（non-uniform）計(jì)算模型的代表。而計(jì)算資源與計(jì)算模型是相關(guān)的，如對(duì)圖靈機(jī)我們一般討論的是時(shí)間、空間和隨機(jī)源，而對(duì)電路我們一般討論電路的大小。由邱奇-圖靈論題（Church-Turingthesis），所有的一致的計(jì)算模型與圖靈機(jī)在多項(xiàng)式時(shí)間意義下是等價(jià)的。而由于我們一般將多項(xiàng)式時(shí)間作為有效算法的標(biāo)志，該論題使得我們可以僅僅關(guān)注圖靈機(jī)而忽略其它的計(jì)算模型。例1：可滿足性（Satisfiability）問題布爾變量集合布爾變量和稱為文字子句集合子句是一些文字的析取（邏輯或）真值賦值給定U和C，是否存在滿足C的真值賦值？可滿足：C中所有的子句在t下為真計(jì)算復(fù)雜度：例2：貨郎擔(dān)問題

（Travelingsalesmanproblem)給定n個(gè)城市，任意兩個(gè)城市間有路相連，一個(gè)貨郎從一個(gè)城市出發(fā)，不重復(fù)的遍歷所有的城市并回到起點(diǎn)，求一條路程最短的路徑。加權(quán)完全圖，，，求Hamilton圈

，使得計(jì)算復(fù)雜度：用有限時(shí)間可以求解，但計(jì)算時(shí)間太長，成本太高優(yōu)化技術(shù)與方法計(jì)算量(1)＋,－,×,÷比較：≠，≤，≥，＜，＞5種基本演算都是用1step

可以實(shí)現(xiàn).實(shí)際上,×比＋多占用時(shí)間.「四舍五入」不算基本演算.

計(jì)算量(2)｛a1,a2,...,an｝：n個(gè)整數(shù)Q1.

求和（1）：

a1+a2+???+an.

n-1steps→O(n)算法.Q2.

求和（2）：

(1)2×a1+???+2×an,2n-1steps→O(n)算法.(2)2×(a1+???+an)

,nsteps→O(n)算法.計(jì)算量(3)Q3.

計(jì)算：a1b1+???+anbn.

2n-1steps.Q4.2個(gè)ｎ×ｎ階矩陣相乘.

n2(2n-1)steps（n2(n+n-1)）.計(jì)算量(4)Q5.｛a1,a2,...,an｝：n個(gè)整數(shù)

求其和為最大的部分集合.

所有的部分集合的和進(jìn)行比較2n(n-1)+(2n-1)→O(n2n)算法.計(jì)算量的膨脹(1)10行×10列棋盤上米粒的數(shù)量（第1格內(nèi)放1粒米，以后每格順次增加1倍……)格序號(hào)米粒數(shù)重量(kg)112.0×10-592565.1×10-3181310722.6×10027671088641.3×10336343597383686.9×10545175921860444163.5×1085490071992547409921.8×10116346116860184273879049.2×10137223611832414348226068484.7×10168112089258196146291747061762.4×10202.4×108億噸計(jì)算量的膨脹(2)100MIPS(megainstructionspersecond)1秒間100萬回的計(jì)算＝1step用10-6秒光速3.0×1010cm/秒(10-6秒

行進(jìn)300m)n101001,00010,000n10-5秒10-4秒10-3秒0.01秒n210-4秒0.01秒1秒100秒n30.001秒

1秒16.6分277時(shí)間2n0.001秒1014世紀(jì)10284世紀(jì)n!0.036秒10141世紀(jì)102551世紀(jì)宇齡：

宇宙的年齢1.5×108世紀(jì)（１５０億年）計(jì)算機(jī)速度增加的效果（1）10秒間的計(jì)算量？100MIPS10倍100倍1000倍

n1071081091010n23千1萬

3萬

10萬n3215462

1千

2千2n2327

30

33

n!101112131000倍?1step用10-9秒?

10-9秒光可以行進(jìn)30cm計(jì)算機(jī)速度增加的效果（2）計(jì)算速度1秒可以求解問題的規(guī)模

O(2n)O(n)O(n2)O(n5)O(n10)100100100100100101200141115107103100031615812610710000100025115811010000031623982001131000000100006312511000001171000000031623100031610000001201000000001000001585398平行（并列）計(jì)算的場合0.5cm見方小碎片，覆蓋地球表面需要2.0×1019個(gè).與100MIPS的單個(gè)計(jì)算機(jī)相比，能加速多少？n1001,000.2n1014世紀(jì)→0.85秒10284世紀(jì)→10263世紀(jì)n!10141世紀(jì)→10120世紀(jì)102551世紀(jì)→102530世紀(jì)問題與算法每個(gè)問題都可能有多個(gè)算法存在．每個(gè)算法的計(jì)算量（速度）都不同。例：贗品金幣問題：問題：9個(gè)外觀完全一樣的金幣.，有一個(gè)是假的（重量輕）．提問：用天秤來鑒別真?zhèn)?，天秤需要使用幾次？贋品金幣問題算法使用2次天秤,就可以鑒別出假幣.789１23456左邊軽右邊軽平衡１23中有偽幣789中有偽幣456中有偽幣左邊軽１32右邊軽平衡１32456789計(jì)算量的表示法:上界值表示法O記號(hào)：(BigONotation)定義:O(f(n))讀作orderf(n),或階f(n)即：g(n)=O(f(n))表示對(duì)于任意定數(shù)c和m，以及對(duì)所有n＞m，有下式成立：g(n)＜cf(n)計(jì)算量的表示法——例n２+1000n→O(n２)logn+n3+1000n2→O(n3)判斷：n!→O(nn)？10n2→

O(n3)？logn→

O(n)？思考：O()?優(yōu)化問題的規(guī)模表示優(yōu)化問題大小的參數(shù)例如：旅行商問題：都市的個(gè)數(shù);背包問題：物品的個(gè)數(shù)注：參數(shù)的個(gè)數(shù)并不僅限于1個(gè)InputSize多項(xiàng)式時(shí)間算法與指數(shù)時(shí)間算法指數(shù)時(shí)間算法=用問題規(guī)模的指數(shù)函數(shù)來表示計(jì)算時(shí)間的算法非有效算法的代名詞多項(xiàng)式時(shí)間算法=能用問題規(guī)模的多項(xiàng)式函數(shù)來表示計(jì)算時(shí)間的算法高效率算法的代名詞多項(xiàng)式時(shí)間算法的計(jì)算時(shí)間問題規(guī)模計(jì)算時(shí)間1020304050100100010000100MIPS(millioninstructionspersecond)計(jì)算機(jī)的情形指數(shù)時(shí)間算法的計(jì)算時(shí)間100MIPS(millioninstructionspersecond)計(jì)算機(jī)的情形問題規(guī)模計(jì)算時(shí)間10203040501001宙齢=150億年指數(shù)災(zāi)難：計(jì)算量的指數(shù)增長指數(shù)災(zāi)難能否避免？SAT問題，貨郎擔(dān)問題，背包問題，圖著色問題，最長路徑問題，……是否對(duì)于每個(gè)問題都有好的算法？什么是好的算法？什么是算法？算法的定義為實(shí)現(xiàn)某個(gè)任務(wù)而構(gòu)成的簡單指令集有窮的計(jì)算良過程通過有限多次運(yùn)算可以決定的過程正確直觀，非形式算法的定義希爾伯特第十問題（1900）設(shè)計(jì)一個(gè)算法來判斷多項(xiàng)式是否有整數(shù)根算法：通過有限多次運(yùn)算可以決定的過程AlanTuring&AlonzoChurch（1936）圖靈機(jī)程序算法：圖靈機(jī)程序形式化的，精確的圖靈機(jī)（TuringMachine)帶子可讀可寫無限長的帶子讀寫頭可左移右移

有限狀態(tài)控制器1111110000000BBB1…………圖靈機(jī)（TuringMachine)TM運(yùn)行由確定:當(dāng)前狀態(tài)為q，所讀字符為s

，讀寫頭不變，，，讀寫頭左移一格，s不變，，讀寫頭右移一格，s不變，無定義，則停機(jī)Church-Turing論題：凡是可計(jì)算的過程都可用圖靈機(jī)實(shí)現(xiàn)；旅行商問題的計(jì)算量（1）n個(gè)都市訪問的可能的巡回路線：n!的Stirling近似公式BigOh記法

的定數(shù)倍的大小可以忽略≈旅行商問題的計(jì)算量（2）根據(jù)Stirling公式以及O（）表示法O（nn）排序問題的計(jì)算量（1）：排序問題：S=｛a1,a2,...,an｝，n個(gè)整數(shù)列，按數(shù)值大小排列dataS輸入

需O(n)時(shí)間；可能的排列種類數(shù)n!種；算法中每一個(gè)比較,都增加2倍的情形數(shù)2分樹的高度（比較的次數(shù)）,

log2(n!)=O(nlog

n)x＞y?yesnon!種可能的排列排序問題計(jì)算量（2）總計(jì)算時(shí)間的復(fù)雜性：O(nlog

n)dataS輸入時(shí)間(或賦值時(shí)間)：O(n)

比較時(shí)間：O(nlog

n)上位取整計(jì)算量的確定例：背包問題的貪婪算法（greedyalgorithm）的計(jì)算量確定計(jì)算量的確定計(jì)算量的確定計(jì)算量的確定計(jì)算量的確定計(jì)算量的確定計(jì)算量的確定計(jì)算的復(fù)雜度時(shí)間復(fù)雜度：

計(jì)算量:計(jì)算各基本操作的實(shí)行回?cái)?shù)（timecomplexity）空間復(fù)雜度各計(jì)算時(shí)點(diǎn)內(nèi)存中保持?jǐn)?shù)據(jù)個(gè)數(shù)的最大值（spacecomplexity）兩者的總稱：計(jì)算的復(fù)雜度計(jì)算復(fù)雜度的影響因素探索空間1---解的近似度、滿意度例：0—10之間的整數(shù)解：1-9共9個(gè)可行解（一維）0—10之間的實(shí)數(shù)解：精確到小數(shù)點(diǎn)后6位共有107個(gè)可行解（一維）；107n個(gè)可行解（n維）探索空間2---解空間大小例：桌子上有6根火柴，要求構(gòu)建出4個(gè)三角形。計(jì)算復(fù)雜度的影響因素探索策略的選取計(jì)算復(fù)雜度的影響因素問題本身P問題NP問題（NP-hard，NP困難問題）NP完全問題

P類 （Polynomial) 判定問題：只有肯定和否定兩種答案優(yōu)化問題可以化作判定問題處理P類具有多項(xiàng)式時(shí)間算法的判定問題形成的計(jì)算復(fù)雜性類猜測TSP（Travelingsalesmanproblem)不屬于P（J.Edmonds1965）

Pclassproblem:能用多項(xiàng)式時(shí)間算法求解的問題的集合稱為P（polynomial）問題某一個(gè)問題屬于P問題的証明某一個(gè)問題不屬于P問題的証明如能夠找到一個(gè)多項(xiàng)式時(shí)間算法

（簡単）不存在？沒找到？（困難）優(yōu)化問題的分類（1）NP類(NondeterministicPolynomial)NP問題：在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可驗(yàn)證的問題P類包含于NP類中NP類問題在確定圖靈機(jī)上指數(shù)時(shí)間可解非確定型圖靈機(jī)和確定型圖靈機(jī)的計(jì)算能力相當(dāng)優(yōu)化問題的分類（2）

NPclassproblem:尚未確信能否用多項(xiàng)式時(shí)間算法求解的問題的集合稱為NP（non-deterministicpolynomial）問題某一個(gè)問題不屬于NP問題的証明某一個(gè)問題屬于NP問題的証明如能夠找到一個(gè)多項(xiàng)式時(shí)間算法

（簡単）可以歸結(jié)為某一類既知的NP類問題（現(xiàn)階段7類））優(yōu)化問題的分類（3）（根據(jù)算法）

NP-completeproblem:集合NP中的問題=NP問題如果某個(gè)NP問題能夠求解，則因所有NP問題都可以經(jīng)過歸結(jié)，轉(zhuǎn)化為該問題，從而可以求解所有NP問題。這樣的NP問題=NP完全問題——集合NP中的最難的問題=

NP完全問題計(jì)算難度比較的標(biāo)準(zhǔn)難易是比較而言的多項(xiàng)式時(shí)間歸約（Karp歸約1972)定義問題A多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為問題B的特殊情況，則稱A可多項(xiàng)式歸約于B，記為轉(zhuǎn)化時(shí)間為多項(xiàng)式對(duì)于A的輸入I的回答與其對(duì)應(yīng)的B的輸入f(I)一致NP完全與NP-hardNP完全問題：NP-hard問題：NP完全問題第一個(gè)NP完全問題（Cook定理1971）可滿足性問題是NP完全問題六個(gè)NP完全問題（Karp1972)3SAT，3DM，VC，團(tuán)，HC，劃分更多的NP完全問題1979年：300多個(gè)1998年：2000多個(gè)P、NP、NP完全的包容關(guān)系NPNP完全旅行商問題背包問題。。。P最短路問題線性規(guī)劃問題。。。NP=PNP完全大多數(shù)研究者認(rèn)可的包容關(guān)系這種可能性也存在（現(xiàn)階段無法證明）懸賞$100萬求證NP完全問題第一個(gè)NP完全問題（Cook定理1971）可滿足性問題是NP完全問題六個(gè)NP完全問題（Karp1972)3SAT，3DM，VC，團(tuán)，HC，劃分更多的NP完全問題1979年：300多個(gè)1998年：2000多個(gè)現(xiàn)在的估計(jì)如果，則指數(shù)災(zāi)難無法避免P=?NP（P-NP問題）P=NPPNPCNP如何處理NP完全問題

實(shí)際的問題不會(huì)消失油井勘探問題移動(dòng)通訊中的頻率分配問題并行計(jì)算以硬件設(shè)備換取時(shí)間存在著很多種并行計(jì)算模型理想模型PRAM可多項(xiàng)式時(shí)間解NP完全問題實(shí)際中效果不好處理器數(shù)目是受限的現(xiàn)實(shí)的代價(jià)：通訊，同步，……分布式計(jì)算算法的研究隨機(jī)算法判定問題：以較大概率得到正確輸出輸出正確，但計(jì)算時(shí)間不定優(yōu)化問題：輸出解的性能不穩(wěn)定