Decision Problem

释义 Definition

决策问题 / 判定问题：在数学逻辑与计算机科学中，指一种只有“是/否”（真/假）答案的问题；关注的是是否存在一种算法，能对任意输入在有限时间内给出正确的是/否结论。（在可计算性理论里常与“可判定性”相关；在复杂性理论里也常讨论其时间/空间开销。）

例句 Examples

A decision problem has a yes-or-no answer.
决策问题只有“是或否”的答案。

Determining whether a given program will halt on a particular input is a famous decision problem in computability theory.
判断某个程序在特定输入下是否会停机，是可计算性理论中著名的一个决策问题。

发音 Pronunciation (IPA)

/dsn prblm/

词源 Etymology

decision 来自拉丁语 decidere（“切开、决定”），引申为“作出决定”；problem 来自希腊语 problēma（“抛到前面的东西、难题”）。合起来的 decision problem 在20世纪数理逻辑与早期计算理论发展中被固定用来指代“可通过程序对任意输入作出是/否判定的一类问题”。

相关词 Related Words

• Algorithm
• Decidability
• Decision Procedure
• Complexity
• Undecidable
• Turing Machine
• Halting Problem

文学与名著用例 Literary Works

• Introduction to the Theory of Computation（Michael Sipser）：用大量篇幅讨论可判定/不可判定的decision problems。
• Gdel, Escher, Bach: An Eternal Golden Braid（Douglas Hofstadter，《哥德尔、艾舍尔、巴赫》）：在谈到形式系统与计算边界时提及经典判定问题。
• Computability and Logic（George S. Boolos, John P. Burgess, Richard C. Jeffrey）：以决策问题为主线之一介绍可计算性与逻辑。