計算複雜性理論
數學理論 / 維基百科,自由的 encyclopedia
計算複雜性理論(Computational complexity theory)是理論電腦科學和數學的一個分支,它致力於將可計算問題根據它們本身的複雜性分類,以及將這些類別聯絡起來。一個可計算問題被認為是一個原則上可以用電腦解決的問題,亦即這個問題可以用一系列機械的數學步驟解決,例如演算法。
如果一個問題的求解需要相當多的資源(無論用什麼演算法),則被認為是難解的。計算複雜性理論通過引入數學計算模型來研究這些問題以及定量計算解決問題所需的資源(時間和空間),從而將資源的確定方法正式化了。其他複雜性測度同樣被運用,比如通訊量(應用於通訊複雜性),電路中門的數量(應用於電路複雜性)以及中央處理器的數量(應用於平行計算)。計算複雜性理論的一個作用就是確定一個能或不能被電腦求解的問題的所具有的實際限制。
在理論電腦科學領域,與此相關的概念有演算法分析和可計算性理論。兩者之間一個關鍵的區別是前者致力於分析用一個確定的演算法來求解一個問題所需的資源量,而後者則是在更廣泛意義上研究用所有可能的演算法來解決相同問題。更精確地說,它嘗試將問題分成能或不能在現有的適當受限的資源條件下解決這兩類。相應地,在現有資源條件下的限制正是區分計算複雜性理論和可計算性理論的一個重要指標:後者關心的是何種問題原則上可以用演算法解決。