跳转到内容

決定性問題

本页使用了标题或全文手工转换
维基百科,自由的百科全书
(重定向自判定性问题
对于判定性问题而言,任何一个输入的输出要么是是(yes),要么是否(no)

可計算性理論計算複雜性理論中,決定性問題,亦稱判定問題,(英語:Decision problem)是一個在某些形式系統回答「是」或「否」的問題。

舉例來說,「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是:「給兩個數字 xyx 是否可以整除 y?」,此問題依據其 xy 的值可回答。以演算法形式給出的解決決定性問題的方法稱為決策程式decision procedure)。對決定性問題「給兩個數字 xyx 是否可以整除 y?」決策程式將確定 x 是否整除 y。一種這樣的演算法是長除法,如果餘數為 0,則原決定性問題的答案為「是」,否則為「否」。若某決定性問題可以被一些演算法所解決,則稱此問題可決定decidable)。

決定性問題與功能性問題Function problem,或複雜型問題)密切相關,與決定性問題相比,功能性問題的答案內容會複雜許多,並非較簡單的是與非。範例問題:「給予一個正整數x,則哪些數可整除 x?」

另一個與上述兩類問題相關的是最佳化問題Optimization problem),此問題關心的是尋找特定問題的最佳答案。

計算複雜度的領域中,分類可決定問題的依據在於「此問題有多難被解決」。在此標準下,所謂的「難」是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中,非決定性問題由圖靈度決定,指的是一種在任何解答中隱含的不可計算性量詞。

計算性理論的研究集中在決定性問題上。在§ 與函數問題的等價性中,並沒有失去其普遍性。

定義

[编辑]

決定性問題指的是在一個數量為無限大的輸入集合中,可產出任何是或非解答的問題之集合。因此傳統上定義決定性問題,乃依其解答為「是」的輸入之集合。在此情形下,一決定性問題亦等於一形式語言

形式上,決定性問題是一自然數子集A。藉由使用哥德尔数,也可學習諸如形式語言的其他集合。非正規的定義決定性問題,就是判別一個給予的數字是否在此集合內。

一決定性問題若其A是一個递归集合,則稱做可決定的(decidable)或有效可解(effectively solvable)。若其A是一递归可枚举集合則稱為部分可決定的(partially decidable)、半可決定的(semidecidable)、可解的(solvable)或可證明(provable)。除此之外,此問題稱為不可決定的

例子

[编辑]

一個經典可決定的決定性問題是質數問題。藉由測試每一個可能的因數,有可能有效決定一個自然數是否為質數。儘管存在很多效能更佳的質數判定方法,任何有效方法的存在就已足夠建立可決定性。

重要的不可決定的決定性問題包括停機問題,其他請見不可決定的問題列表。在計算複雜性理論中,完備的決定性問題通常用來判別其他決定性問題的複雜度類別。重要的實例包括SAT問題與其數變種,還有無向有向圖可達性問題

歷史

[编辑]

德语“Entscheidungsproblem”,亦即“判定性问题”(Decision-problem),最早出自于大衞·希尔伯特的话:“在1928年的会议上,希尔伯特精确地描述了他的问题。首先,数学是否具有完备性?……其次,数学是否具有相容性?……再次,数学是否具有判定性?这些问题的意思是,是否存在这样一种确定的方法,在理论上可适用于任何假设,并且能够保证对无论是否正确的假设都能给出一个正确的结果”(Hodeges,p. 91)。希尔伯特相信“在数学上没有‘ignorabimus’”,亦即“我们将无从得之”。

與函數問題的等價性

[编辑]

參考

[编辑]
  • 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.
  • Kozen, D.C.(1997), Automata and Computability, Springer.
  • Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
  • Sipser, M.(1996), Introduction to the Theory of Computation, PWS Publishing Co.
  • Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7