標籤: 暫無標籤

理論計算機科學中的一個重要概念。各種計算機器模型(自動機),在每一時刻,根據當時的狀態和輸入,若機器的動作可唯一確定時,則稱機器為確定性的;若有多個動作可供選擇時,則稱機器為非確定性的

1 非確定性 -非確定性

2 非確定性 -簡介

理論計算機科學中的一個重要概念。各種計算機器模型(自動機),在每一時刻,根據當時的狀態和輸入,若機器的動作可唯一確定時,則稱機器為確定性的;若有多個動作可供選擇時,則稱機器為非確定性的。任意一種自動機,按其動作的確定程度,大體可分為確定的和非確定的兩類。在對非確定性的研究中,一個核心課題就是非確定性能否增加機器的計算能力。具體說,對同一類自動機,確定型和非確定型機器在計算能力方面有沒有區別?是什麼關係?這類問題因其在理論上和實踐中的重要意義而受到普遍重視。其中有些問題至今尚未解決,成為理論計算機科學中重要的懸案,NP=?P問題就是一個突出的例子。

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

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

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

3 非確定性 -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中就將會有一批實際問題不是現實可計算的。

4 非確定性 -非確定性在學術文獻中的解釋

1、2.非確定性所謂的非確定性是指事件發生的可能性完全不可知的情形.更確切地,是指沒有概率分佈能與所考察的事件的結果相聯繫的情形 
 
2、1.2化石能源開發利用的非確定性所謂非確定性,是指現實決策對未來影響的不準確預見.這在化石能源的開發利用過程中是不可避免的  
 

5 非確定性 -配圖

6 非確定性 -相關連接

上一篇[蘇梅克-列維9號彗星]    下一篇 [何庸]

相關評論

同義詞:暫無同義詞