複雜性理論
出自 MBA智库百科(https://wiki.mbalib.com/)
複雜性理論（Complexity Theory）
目錄 |
複雜性理論是理論電腦科學和數學的一個分支，它致力於將可計算問題根據它們本身的複雜性分類，以及將這些類別聯繫起來。一個可計算問題被認為是一個原則上可以用電腦解決的問題，亦即這個問題可以用一系列機械的數學步驟解決，例如演算法。
在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領域最早的文獻。而一般說來，被公認為奠定了計算複雜性領域基礎的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領域最早的文獻。而一般說來，被公認為奠定了計算複雜性領域基礎的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間複雜性類TIME(f(n))的概念，並利用對角線法證明瞭時間層級定理（Time Hierarchy Theorem）。
在此之後，許多研究者對複雜性理論作出了貢獻。期間重要的發現包括：對隨機演算法的去隨機化（derandomization）的研究，對近似演算法的不可近似性（hardness of approximation）的研究，以及互動式證明系統理論和零知識證明（Zero-knowledge proof）等。特別的複雜性理論對近代密碼學的影響非常顯著，而最近，複雜性理論的研究者又進入了博弈論領域，並創立了“演算法博弈論”（algorithmic game theory）這一分支。
所謂複雜性理論，從根本上說就是研究哪些工作可以很容易地用電腦完成，哪些工作不能的理論。在複雜性理論中，最關鍵的事情是搞清楚隨著輸入數據的增長，解決一個問題所需的步驟會以什麼樣的方式增加。
如果一個問題的求解需要相當多的資源（無論用什麼演算法），則被認為是難解的。計算複雜性理論通過引入數學計算模型來研究這些問題以及定量計算解決問題所需的資源（時間和空間），從而將資源的確定方法正式化了。其他複雜性測度同樣被運用，比如通信量（應用於通信複雜性），電路中門的數量（應用於電路複雜性）以及中央處理器的數量（應用於並行計算）。計算複雜性理論的一個作用就是確定一個能或不能被電腦求解的問題的所具有的實際限制。
在理論電腦科學領域，與此相關的概念有演算法分析和可計算性理論。兩者之間一個關鍵的區別是前者致力於分析用一個確定的演算法來求解一個問題所需的資源量，而後者則是在更廣泛意義上研究用所有可能的演算法來解決相同問題。更精確地說，它嘗試將問題分成能或不能在現有的適當受限的資源條件下解決這兩類。相應地，在現有資源條件下的限制正是區分計算複雜性理論和可計算性理論的一個重要指標：後者關心的是何種問題原則上可以用演算法解決。
複雜性理論所研究的資源中最常見的是時間（要通過多少步演算才能解決問題）和空間（在解決問題時需要多少記憶體）。其他資源亦可考慮，例如在並行計算中，需要多少並行處理器才能解決問題。時間複雜度是指在電腦科學與工程領域完成一個演算法所需要的時間，是衡量一個演算法優劣的重要參數。時間複雜度越小，說明該演算法效率越高，則該演算法越有價值。空間複雜度是指電腦科學領域完成一個演算法所需要占用的存儲空間，一般是輸入參數的函數。它是演算法優劣的重要度量指標，一般來說，空間複雜度越小，演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有X個字（word）屬於這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。
複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和演算法理論是一種“矛”與“盾”的關係，即演算法理論專註於設計有效的演算法，而複雜性理論專註於理解為什麼對於某類問題，不存在有效的演算法。
