非確定性
簡介
理論計算機科學中的一個重要概念。各種計算機器模型（自動機），在每一時刻，根據當時的狀態和輸入，若機器的動作可唯一確定時，則稱機器為確定性的；若有多個動作可供選擇時，則稱機器為非確定性的。任意一種自動機，按其動作的確定程度，大體可分為確定的和非確定的兩類。在對非確定性的研究中，一個核心課題就是非確定性能否增加機器的計算能力。具體說，對同一類自動機，確定型和非確定型機器在計算能力方面有沒有區別？是什麼關係？這類問題因其在理論上和實踐中的重要意義而受到普遍重視。其中有些問題至今尚未解決，成為理論計算機科學中重要的懸案,NP=?P問題就是一個突出的例子。
一個單帶圖靈機，由一個有限控制器、一條輸入帶和相應的讀寫頭組成。圖靈機的動作是由有限控制器的狀態和讀寫頭掃視方格中的符號，依一定規則來定的。每一動作包括：改變機器的狀態；在讀寫頭掃視的方格中列印一個符號,以代替原來的符號;讀寫頭向左或向右移一個方格。對於給定的狀態和讀寫頭讀到的符號，圖靈機的下一動作可能是唯一確定的，也可能有有窮多個動作可供選擇。如果對於任何狀態-符號對,下一動作都是唯一的，這種機器稱為確定型單帶圖靈機；如果有有窮多個（包括零個或一個的情形）可以任意選擇的下一動作，且規定對於給定的輸入，只要在所有可能的動作序列中有一個序列導致接受狀態,機器就接受其輸入,這種機器就稱為非確定型單帶圖靈機。對於確定型和非確定型的其他類型自動機，均可以類似地給出定義。
對於同一類型的自動機，確定型可以看作是非確定型的特殊情形。因此，非確定型的計算能力一般說應比確定型的強。然而是否真強，則取決於所討論的自動機的類型。從自動機接受語言（見形式語言理論）的能力來說，對於有限自動機，確定型機器和非確定型機器接受的語言類完全一樣，都是正規集合。對於下推自動機，確定型機器接受的語言類（確定的上下文無關語言）是非確定型機器接受的語言類（上下文無關語言）的真子類。例如，L=｛0i1j2k|i=j或j=κ｝就是一個屬於後者而不屬於前者的語言。對於線性有界自動機，確定型機器和非確定型機器接受能力是否相等的問題，至今尚未解決,這就是著名的“LBA問題”。對於圖靈機,已經證明確定機器與非確定機器具有相同的接受能力，它們所接受的語言類都是遞歸可枚舉集合。
在計算複雜性理論中不僅考慮能不能計算的問題，還考慮計算時耗費資源（時間、空間等）的數量。在圖靈機的情況下，如考慮資源界限，則對計算能力問題的回答便不一樣。例如，當考慮多項式空間界限時，確定型圖靈機接受的語言類pSpace和非確定型圖靈機接受的語言類 NPSPACE是相同的。而當考慮多項式時間界限時，就產生了著名的“NP=?P問題”。
NP＝?P問題
確定型圖靈機在多項式時間內接受的語言所組成的類,記作P；非確定型圖靈機在多項式時間內接受的語言所組成的類，記作NP。後者包含前者，但兩者是否相同這個問題至今仍未解決。
關於NP=?P問題的研究,大體有四方面工作：藉助歸約方法進行的NP完全性理論的研究;藉助ORACLE(橡樹嶺自動計算機和邏輯機)進行的相對化語言類的研究;結合各種語言時間（空間）複雜性類進行的研究；細分非確定性、可證明 NP和P等其他方面的研究。在研究過程中，有人試圖證明NP=P;更多的則猜測併力圖證明NP
P。有越來越多的人趨向於認為：NP＝?P問題是獨立於公理系統的，即在通常的公理化系統中，既不能證明NP=P，也不能否證它。
這個問題的研究，在理論和實踐兩個方面都具有重要意義。從理論上說，它使人們對非確定性這樣一個重要概念的本質，有了越來越深的認識。同時,隨著NP=?P問題研究的深入，引出了許多新的理論問題，它們都程度不同地和NP＝?P問題相關。一旦NP＝?P問題獲得解決，就會導致一系列理論問題的解決。
其次，實踐中的大量問題不是屬於 P，就是屬於NP。儘管圖靈機能解決的問題都是可計算的,但普遍認為,只有屬於 P的問題才是在計算機上現實可計算的。需要指數時間的問題雖然可計算，但因需要太多的時間，以致不被認為是現實可計算的。NP＝?P問題就成為直接關係到NP中相當一批實際問題是否是“現實可計算的”這樣一個大問題。實際上,若NP＝P，那么NP中一切問題都是現實可計算的；但若NP厵P,NP中就將會有一批實際問題不是現實可計算的。
非確定性在學術文獻中的解釋
1、2.非確定性所謂的非確定性是指事件發生的可能性完全不可知的情形.更確切地,是指沒有機率分布能與所考察的事件的結果相聯繫的情形
2、1．2化石能源開發利用的非確定性所謂非確定性,是指現實決策對未來影響的不準確預見.這在化石能源的開發利用過程中是不可避免的
