决定性问题
维基百科,自由的 encyclopedia
在可计算性理论与计算复杂性理论中,决定性问题,亦称判定问题,(英语:Decision problem)是一个在某些形式系统回答“是”或“否”的问题。
举例来说,“判定给定的自然数是否为素数”是一个决定性问题。另一个具体的例子是:“给两个数字 x 与 y,x 是否可以整除 y?”,此问题依据其 x 与 y 的值可回答是或否。以算法形式给出的解决决定性问题的方法称为决策程序(decision procedure)。对决定性问题“给两个数字 x 与 y,x 是否可以整除 y?”决策程序将确定 x 是否整除 y。一种这样的算法是长除法,如果余数为 0,则原决定性问题的答案为“是”,否则为“否”。若某决定性问题可以被一些算法所解决,则称此问题可决定(decidable)。
决定性问题与功能性问题(Function problem,或复杂型问题)密切相关,与决定性问题相比,功能性问题的答案内容会复杂许多,并非较简单的是与非。示例问题:“给予一个正整数x,则哪些数可整除 x?”
另一个与上述两类问题相关的是优化问题(Optimization problem),此问题关心的是查找特定问题的最佳答案。
计算复杂度的领域中,分类可决定问题的依据在于“此问题有多难被解决”。在此标准下,所谓的“难”是以解决某问题最有效率的算法所花费的计算资源为依据。在递归理论中,非决定性问题由图灵度决定,指的是一种在任何解答中隐含的不可计算性量词。
计算性理论的研究集中在决定性问题上。在§ 与函数问题的等价性中,并没有失去其普遍性。