-
決定性問題
鎖定
- 中文名
- 決定性問題
- 外文名
- Decision problem
- 概 念
- 在某些形式系統回答是或否的問題
決定性問題綜述
決定性問題在數學問題是否“可決定”中出現,即是否存在有效方法判定一個性質的存在性。數學中許多重要的問題都是不可決定的。
決定性問題與功能性問題(Function problem)(或複雜型問題)密切相關,功能性問題的答案內容,較簡單的是比“與非”複雜很多。範例問題:“給予一個正整數x,則哪些數可整除x?”
另一個與上述兩類問題相關的是最佳化問題,此問題關心的是尋找特定問題的最佳答案。
計算複雜度的領域中,分類可決定問題的依據在於此問題有多難被解決。在此標準下,所謂的難是以解決某問題最有效率的算法所花費的計算資源為依據。在遞歸理論中,非決定性問題由圖靈度(不可解度)決定,指的是一種在任何解答中隱含的不可計算性量詞。
計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中,並沒有失去其普遍性。
一個判斷決定性的重要手段是萊斯定理(Rice's Theorem)。
決定性問題定義
決定性問題指的是在一個數量為無限大的輸入集合中,可產出任何是或非解答的問題之集合。因此傳統上定義決定性問題,乃依其解答為是的輸入之集合。在此情形下,一決定性問題亦等於一形式語言。
形式上,決定性問題是一自然數子集A。藉由使用哥德爾數,也可學習諸如形式語言的其他集合。非正規的定義決定性問題,就是判別一個給予的數字是否在此集合內。
決定性問題例子
一個經典可決定的決定性問題是質數問題。藉由測試每一個可能的因子,有可能有效決定一個自然數是否為質數。儘管存在很多效能更佳的質數判定方法,任何有效方法的存在就已足夠建立可決定性。
決定性問題可決定性
一決定性問題A,若A是一個遞歸集合,則稱做可決定的(decidable)或有效可解(effectively solvable)。若其A是一遞歸可枚舉集合則稱為部分可決定的(partially decidable)、半可決定的(semidecidable)、可解的(solvable)或可證明(provable)。除此之外,此問題稱為不可決定的。
重要的不可決定的決定性問題包括停機問題。
決定性問題完備性
決定性問題可以利用多至一簡化(Many-one reduction)以及其他相關的簡化如多項式時間簡化(Polynomial-time reduction)來分類。一個決定性問題P被稱為完備的,只要有一個集合包含一組決定性問題S,集合裏所有問題都可以簡化為P。完備的決定性問題一般用於計算複雜性理論來分決定性問題於複雜性類。例如布爾可滿足性問題對於決定性問題中的NP問題在多項式時間簡化下是完備的。
決定性問題歷史
德語“Entscheidungsproblem”,亦即“判定性問題”(Decision-problem),最早出自於大衞·希爾伯特的話:“在1928年的會議上,希爾伯特精確地描述了他的問題。首先,數學是否具有完備性?……其次,數學是否具有相容性?……再次,數學是否具有判定性?這些問題的意思是,是否存在這樣一種確定的方法,在理論上可適用於任何假設,並且能夠保證對無論是否正確的假設都能給出一個正確的結果”(Hodeges,p. 91)。希爾伯特相信“在數學上沒有‘ignorabimus’”,亦即“我們將無從得之”。
[1]
決定性問題與功能性問題的等價性
一個功能性問題是由一個局部函數f組成的,這個非正式的“問題”是計算f在它定義下的值。
所有功能性問題可以轉化成決定性問題;這個決定性問題是這個函數的圖(函數f的圖是指數對(x,y)有f(x)=y),如果這個決定性問題是可解的,那麼這個功能性問題同樣可解。這個簡化沒有考慮計算複雜性,比如劃歸後在多項式時間可決定的函數(運算時間是根據函數(x,y)計算的)不一定在多項式時間內可計算(這時只對x計算),函數f=2^x就有這種性質。
所有決定性問題也能轉換成功能性問題,就是計算決定性問題集合的特徵函數。如果函數是可計算的,那麼這個問題就是可決定的。然而,這種轉化比在計算複雜性理論裏的轉化(一般叫多至一多項式時間轉化)更加自由。
[2]
- 參考資料
-
- 1. Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7
- 2. Hodges, A., Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for some more history that led to Turing's work. Hodges references a biography of David Hilbert: Constance Reid, Hilbert(George Allen & Unwin; Springer-Verlag, 1970). There are apparently more recent editions.
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:7次歷史版本
- 最近更新: 向日葵暖阳66