非確定性

任意一種自動機，按其動作的確定程度，大體可分為確定的和非確定的兩類。在對非確定性的研究中，一個核心課題就是非確定性能否增加機器的計算能力。具體說，對同一類自動機，確定型和非確定型機器在計算能力方面有沒有區別？是什麼關係？這類問題因其在理論上和實踐中的重要意義而受到普遍重視。其中有些問題至今尚未解決，成為理論計算機科學中重要的懸案,NP=?P問題就是一個突出的例子。

一個單帶圖靈機，由一個有限控制器、一條輸入帶和相應的讀寫頭組成。圖靈機的動作是由有限控制器的狀態和讀寫頭掃視方格中的符號，依一定規則來定的。每一動作包括：改變機器的狀態；在讀寫頭掃視的方格中列印一個符號，以代替原來的符號；讀寫頭向左或向右移一個方格。對於給定的狀態和讀寫頭讀到的符號，圖靈機的下一動作可能是唯一確定的，也可能有有窮多個動作可供選擇。如果對於任何狀態-符號對，下一動作都是唯一的，這種機器稱為確定型單帶圖靈機；如果有有窮多個（包括零個或一個的情形）可以任意選擇的下一動作，且規定對於給定的輸入，只要在所有可能的動作序列中有一個序列導致接受狀態，機器就接受其輸入，這種機器就稱為非確定型單帶圖靈機。對於確定型和非確定型的其他類型自動機，均可以類似地給出定義。

對於同一類型的自動機，確定型可以看作是非確定型的特殊情形。因此，非確定型的計算能力一般說應比確定型的強。然而是否真強，則取決於所討論的自動機的類型。從自動機接受語言（見形式語言理論）的能力來說，對於有限自動機，確定型機器和非確定型機器接受的語言類完全一樣，都是正規集合。對於下推自動機，確定型機器接受的語言類（確定的上下文無關語言）是非確定型機器接受的語言類（上下文無關語言）的真子類。例如，L={0i1j2k|i=j或j=κ}就是一個屬於後者而不屬於前者的語言。對於線性有界自動機，確定型機器和非確定型機器接受能力是否相等的問題，至今尚未解決，這就是著名的“LBA問題”。對於圖靈機，已經證明確定機器與非確定機器具有相同的接受能力，它們所接受的語言類都是遞歸可枚舉集合。

在計算複雜性理論中不僅考慮能不能計算的問題，還考慮計算時耗費資源（時間、空間等）的數量。在圖靈機的情況下，如考慮資源界限，則對計算能力問題的回答便不一樣。例如，當考慮多項式空間界限時，確定型圖靈機接受的語言類PSPACE和非確定型圖靈機接受的語言類 NPSPACE是相同的。而當考慮多項式時間界限時，就產生了著名的“NP=?P問題”。

確定型圖靈機在多項式時間內接受的語言所組成的類，記作P；非確定型圖靈機在多項式時間內接受的語言所組成的類，記作NP。後者包含前者，但兩者是否相同這個問題至今仍未解決。

關於NP=?P問題的研究，大體有四方面工作：藉助歸約方法進行的NP完全性理論的研究；藉助ORACLE(橡樹嶺自動計算機和邏輯機)進行的相對化語言類的研究；結合各種語言時間（空間）複雜性類進行的研究；細分非確定性、可證明 NP和P等其他方面的研究。在研究過程中，有人試圖證明NP=P;更多的則猜測并力圖證明NP。有越來越多的人趨向於認為：NP=?P問題是獨立於公理系統的，即在通常的公理化系統中，既不能證明NP=P，也不能否證它。

這個問題的研究，在理論和實踐兩個方面都具有重要意義。從理論上說，它使人們對非確定性這樣一個重要概念的本質，有了越來越深的認識。同時，隨著NP=?P問題研究的深入，引出了許多新的理論問題，它們都程度不同地和NP=?P問題相關。一旦NP=?P問題獲得解決，就會導致一系列理論問題的解決。

其次，實踐中的大量問題不是屬於 P，就是屬於NP。儘管圖靈機能解決的問題都是可計算的，但普遍認為，只有屬於 P的問題才是在計算機上現實可計算的。需要指數時間的問題雖然可計算，但因需要太多的時間，以致不被認為是現實可計算的。NP=?P問題就成為直接關係到NP中相當一批實際問題是否是“現實可計算的”這樣一個大問題。實際上，若NP=P，那麼NP中一切問題都是現實可計算的；但若NP≠P,NP中就將會有一批實際問題不是現實可計算的。