跳转到内容

决定性问题

本页使用了标题或全文手工转换
维基百科,自由的百科全书
对于判定性问题而言,任何一个输入的输出要么是是(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