演演算法複雜性

由於不同的計算機千差萬別，運算速度和字長可以相差很大，因此，不可能用演演算法在某一台計算機上計算所需要的實際的時間和存儲單元（空間）去衡量這個演演算法的複雜性。那麼，怎樣才能準確刻劃演演算法的計算複雜性呢？

引入漸近增長率的概念來刻劃演演算法的計算複雜性。漸進增長率用複雜性度量函數表示，該函數表示了演演算法隨問題規模大小變化引起的演演算法中抽象的基本運算執行的次數或存儲空間量的變化規律。如某個計算問題當輸入規模分別為1，2，3，…，n時，經分析演演算法中抽象的基本運算次數分別為1，4，9，…，n2，那麼，就可以用函數n2來刻劃這個演演算法的時間複雜性，並稱這個演演算法的時間複雜性度量為(n2)級。有了複雜性度量函數，一旦選定具體計算機，可以根據這台計算機對某個n值的實際運算速度比較準確地估算出對其他的n值完成計算所需要的時間。於是，對各種

演演算法的複雜性進行分析的關鍵是要設法去找出這樣的函數，它涉及到與數學密切相關的演演算法的設計原理、思想和方法，演演算法分析是具有智力挑戰性的研究課題。在演演算法計算複雜性的研究中，一個演演算法如果存在圖靈機可計算的多項式時間計算複雜性演演算法，就將這個演演算法歸入P類，如果存在非確定性圖靈機可計算的多項式時間計算複雜性演演算法，就將其歸入NP類。對大多數實際問題來說，找到一個解可能很難，檢驗一個解常常比較容易，所以都屬於NP類。現在，計算科學研究中一個懸而未決的重要問題是P＝NP？。

P＝NP？這個問題不僅具有理論上的價值，而且具有重大實用價值。因為到目前為止，已經發現了一批可計算但有相當難度的問題是屬於NP類的，並且常通過證明一個問題與已知

屬於NP類中的某個問題（如可滿足性問題，簡稱SAT問題）等價將其歸入NP類。不過，該問題是否屬於 P類，即是否能找到多項式時間計算複雜性演演算法求解該問題，或證明該問題不存在多項式時間計算複雜性演演算法求解，至今尚未解決。現在，很多人都猜測秋碧貞楠的看法是對的：求解一個問題總是比驗證一個問題的解要難，用公式表示也就是P≠NP。70年代初，庫克（S. A. Cook）和卡爾普（R. M. Karp）指出，NP類中有一小類問題具有以下性質：迄今為止，這些問題多數經過深思熟慮還沒有人找到多項式時間計算複雜性演演算法。但是，一旦其中的一個問題找到了多項式時間計算複雜性演演算法，這個類中的其它問題也能找到多項式時間計算複雜性演演算法，那麼就可以斷定P＝NP。換句話說，如果確屬這個類中的某個問題被證明不存在多項式時間計算複雜性演演算法，那麼，就等於證明了P≠NP。通常，將這類問題稱為NP完全性問題。