NP Complete問題
複雜度類別 P 是否和 NP 相等 (P=NP?)，是資訊科學領域最吸引人的一個未解問題！
P 即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題
NP 由所有可以在多項式時間內驗證它的解是否正確的決定問題組成，或者等效的說，那些可以在非確定型圖靈機上在多項式時間內找出解的問題的集合。很可能，計算理論最大的未解決問題就是關於這兩類的關係的：
P = NP ?
史蒂芬庫克(Stephen Cook)證明了一個十分重要的性質： 性質(A)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成滿足問題。」 性質(B)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成任一個 NP-complete 問題。」 性質(C)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成任一個 NP-hard 問題。」 性質(D)：「滿足問題在集合 P 中，若且唯若，P=NP。」