計算復雜性理論

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

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

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

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

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

可以實現.實際上,×比＋多占用時間.「四舍五入」不算基本演算.

計算量(2)｛a1,a2,...,an｝：n個整數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)算法.計算量(3)Q3.

計算：a1b1+???+anbn.

2n-1steps.Q4.2個ｎ×ｎ階矩陣相乘.

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

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

所有的部分集合的和進行比較2n(n-1)+(2n-1)→O(n2n)算法.計算量的膨脹(1)10行×10列棋盤上米粒的數量（第1格內放1粒米，以后每格順次增加1倍……)格序號米粒數重量(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億噸計算量的膨脹(2)100MIPS(megainstructionspersecond)1秒間100萬回的計算＝1step用10-6秒光速3.0×1010cm/秒(10-6秒

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

1秒16.6分277時間2n0.001秒1014世紀10284世紀n!0.036秒10141世紀102551世紀宇齡：

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

n1071081091010n23千1萬

3萬

10萬n3215462

1千

2千2n2327

30

33

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

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

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

O(n3)？logn→

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

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

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

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

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

log2(n!)=O(nlog

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

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

比較時間：O(nlog

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

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

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

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

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

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

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

NP-completeproblem:集合NP中的問題=NP問題如果某個NP問題能夠求解，則因所有NP問題都可以經過歸結，轉化為該問題，從而可以求解所有NP問題。這樣的NP問題=NP完全問題——集合NP中的最難的問題=

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

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