非確定性

所謂非確定性是指在理論計算機科學中,針對各種計算機器模型(自動機),在每一時刻,根據當時的狀態和輸入,若機器有多個動作可供選擇時,則稱機器為非確定性的;相反,若機器的動作可唯一確定時。且非確定性是相對於確定性來說,對於非確定性的機器,在性能各方面要高於確定性機器。

  • 中文名稱
    非確定性
  • 核心課題
    非確定性能否增加機器的計算能力
  • 標    準
    動作的確定程度
  • 分    類
    確定的和非確定

簡介

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

例子

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

對於同一類型的自動機,確定型可以看作是非確定型的特殊情形。因此,非確定型的計算能力一般說應比確定型的強。然而是否真強,則取決於所討論的自動機的類型。從自動機接受語言(見形式語言理論)的能力來說,對於有限自動機,確定型機器和非確定型機器接受的語言類完全一樣,都是正規集合。對於下推自動機,確定型機器接受的語言類(確定的上下文無關語言)是非確定型機器接受的語言類(上下文無關語言)的真子類。例如,L={0i1j2k|i=jj=κ}就是一個屬於後者而不屬於前者的語言。對於線性有界自動機,確定型機器和非確定型機器接受能力是否相等的問題,至今尚未解決,這就是著名的"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中就將會有一批實際問題不是現實可計算的。

其它詞條