decision problem（判定问题/决策问题）：指一种计算问题，其输出只有两种可能结果，通常是“是/否”（true/false）。在计算复杂性与可计算性理论中，常用来研究某类问题是否可被算法解决、以及需要多少计算资源。
/dsn prblm/
A yes-or-no question is a decision problem.
“是或否”的问题就是一个判定问题。
In computational complexity, many optimization tasks are first rewritten as a decision problem to classify their difficulty.
在计算复杂性理论中，许多优化任务会先改写成判定问题，以便对其难度进行分类。
decision 来自拉丁语词根，含“裁决、决定”之意；problem 源自希腊语，指“要解决的难题”。组合成 decision problem 时，强调“要做出二选一裁决的问题”，即输出只有两类结果（是/否）的形式。该用法在20世纪数理逻辑、可计算性与计算机科学的发展中被固定下来。
Select Language