1 定义与形式化
1.1 问题实例与答案
决策问题是一类要求对每个具体实例给出“是”或“否”答案的数学问题。每个决策问题由一个无限的可能实例集合构成，每个实例对应一个明确的问题陈述。答案的二元性意味着决策问题的输出空间仅包含两个元素：肯定（通常记为“是”或1）和否定（“否”或0）。例如，“给定一个整数，它是否为素数？”便是一个典型的决策问题，其实例为每个正整数，答案为“是”当且仅当该数是素数。
1.2 语言与判定
在形式化框架中，决策问题常被编码为语言判定问题。设Σ是一个有限字母表，Σ*表示所有有限字符串的集合。一个决策问题对应于一个子集L ⊆ Σ*，称为该问题的语言。给定一个实例编码后的字符串w ∈ Σ*，问题要求判定w是否属于L。此时，决策问题转化为一个函数：f: Σ* → {0, 1}，其中f(w)=1当且仅当w ∈ L。这种编码方式使得计算模型的输入输出统一为字符串，便于利用图灵机、有限自动机等抽象计算模型进行分析。
1.3 归约与等价性
归约是建立决策问题之间关系的重要工具。一个决策问题A可归约到决策问题B（记作A ≤ B），如果存在一个可以在多项式时间内（或更一般的计算资源限制下）计算的函数g，将A的每个实例x映射到B的实例g(x)，使得x是A的肯定实例当且仅当g(x)是B的肯定实例。归约概念用于比较问题的相对难度：如果A可归约到B且B已有一个解法，则通过归约也可解A。当两个问题可互相归约时，称它们在归约意义下等价。等价性问题属于相同的复杂度类，可共用算法设计策略。
2 分类与性质
2.1 可判定性与不可判定性
2.1.1 递归可枚举集
递归可枚举集（又称半可判定集）是指存在一个图灵机，对属于该语言的输入总能停机并回答“是”，但对不属于的输入可能永远不停机。形式上，语言L是递归可枚举的当且仅当存在图灵机M，使得对任意w ∈ L，M(w)最终停机并接受；对任意w ∉ L，M(w)不停机或拒绝。所有可判定问题都是递归可枚举的，但反之不成立——存在递归可枚举但不可判定的问题。
2.1.2 停机问题的不可判定性
停机问题是决策不可判定性的最著名例子。该问题描述为：给定一个图灵机M和一个输入w，判断M在输入w上是否最终停机。阿兰·图灵在1936年通过对角线化论证证明了不存在一个通用算法能正确解答所有停机问题的实例。这一结论表明，即便对于简单的程序行为预测，也存在无法避免的理论极限。停机问题的不可判定性导致了大量其他问题的不可判定性，例如希尔伯特第十问题（整数方程求解）和上下文无关文法的歧义性问题。
2.2 计算复杂度
2.2.1 P类与NP类
P类包含那些存在确定性图灵机能在多项式时间内解决的决策问题。例如，判断一个整数是否为素数（2002年AKS算法证明属于P）。NP类包含那些肯定实例可以在多项式时间内被验证的决策问题，即存在一个多项式时间验证器，对于肯定实例能给出一个“证书”（证明）并验证。例如，判断一个图是否存在哈密顿回路：虽然难以直接找到回路，但如果有人给出一个回路，可以快速验证其正确性。
P是否等于NP是理论计算机科学中最重要的未解决问题之一。直观上，P类问题容易求解，而NP类问题容易验证，但两者关系尚未厘清。
2.2.2 NP完全问题
NP完全问题是NP类中最“难”的问题，具有两个性质：(1) 本身属于NP；(2) 任何其他NP问题都可以多项式时间归约到它。因此，如果任何一个NP完全问题存在多项式时间算法，则P=NP。NP完全性由斯蒂芬·库克于1971年建立。
2.2.2.1 布尔可满足性问题（SAT）
SAT是第一个被证明为NP完全的问题。给定一个布尔公式（由变量、与、或、非构成），问是否存在一组布尔变量赋值使得公式为真。库克-莱文定理指出，任何NP问题都可以编码为SAT实例。SAT的NP完全性奠定了整个NP完全性理论的基础。
2.2.2.2 图着色决策问题
给定一个无向图和一个正整数k，判断能否用至多k种颜色给每个顶点染色，使得相邻顶点颜色不同。该问题对k≥3是NP完全的（k=2时可在多项式时间内解决）。图着色决策问题在调度、寄存器分配等领域有直接应用，其NP完全性意味着寻找最优着色数目（优化版本）同样困难。
2.2.3 其他复杂度类概述
除P与NP外，复杂度类还包括：co-NP（补问题在NP中的类）、PSPACE（多项式空间可解的问题）、EXP（指数时间可解的问题）、L（对数空间可解的问题）等。层次关系通常认为： P ⊆ NP ⊆ PSPACE ⊆ EXP，且所有真包含关系均未严格证明（除P ≠ EXP外）。决策问题的复杂度分类帮助算法设计者识别问题的内在难度，并指导近似算法或启发式策略的使用。
3 典型决策问题举例
3.1 数学逻辑中的决策问题
3.1.1 命题逻辑的可满足性
命题逻辑的可满足性问题即SAT，是逻辑学中最基本的决策问题。由于SAT的NP完全性，它在人工智能、自动推理中扮演核心角色。现代SAT求解器使用冲突驱动子句学习、分支启发式等技术，能处理包含数百万变量的工业实例。
3.1.2 一阶逻辑的判定问题
一阶逻辑的普遍有效性（即公式在所有解释下均为真）是不可判定的，这由丘奇于1936年证明。然而，某些受限片段是可判定的，例如仅含一元谓词的一阶逻辑、有限域上的逻辑、或者仅允许特定量词前缀的片段。一阶逻辑的判定问题在数学基础理论和定理证明自动化中有重要意义。
3.2 图论与组合优化中的决策问题
3.2.1 哈密顿回路问题
给定一个无向图，问是否存在一条经过每个顶点恰好一次并回到起点的回路（哈密顿回路）。该决策问题是NP完全的。尽管哈密顿回路在图中普遍存在（如完全图），但判断任意图是否存在该回路通常需要指数时间。
3.2.2 顶点覆盖问题
给定一个图和一个整数k，问是否存在一个大小为至多k的顶点集合，使得每条边至少有一个端点在该集合中。顶点覆盖是经典的NP完全问题，同时也是固定参数可解（FPT）问题的代表，可通过参数化算法在O(1.618^k + n)时间内求解。
3.3 自动机与形式语言理论
3.3.1 空集判定问题
给定一个自动机（如有限自动机、下推自动机或图灵机），问其接受的语言是否为空。对于不同自动机模型，该问题的可判定性不同：有限自动机的空集问题可在多项式时间内解决；下推自动机的空集问题可判定但为PSPACE完全；图灵机的空集问题不可判定。
3.3.2 包含与等价问题
给定两个自动机，问一个自动机的语言是否包含另一个，或者两者是否等价。对于有限自动机，包含与等价问题均可判定且属于PSPACE（实际上可通过正则语言的性质在多项式时间内解决）；对于上下文无关文法，等价问题不可判定。这些问题在编译器优化和模型检验中至关重要。
4 与其他问题的关系
4.1 决策问题与优化问题
4.1.1 由优化问题转化而来
许多优化问题可以通过添加一个阈值参数转化为决策问题。例如，旅行商问题的优化版本要求找出最短回路，其对应的决策版本为“是否存在长度不超过L的回路”。这种转化使得优化问题的困难程度可以从其决策版本的复杂度推断。一般情况下，如果决策问题是NP完全的，则优化版本也是NP难问题。
4.1.2 决策问题作为子程序
在求解优化问题时，常将决策问题作为子程序用于二分搜索。例如，要寻找图的最小顶点覆盖大小，可以反复调用顶点覆盖决策问题：从k=0开始，若决策问题回答“否”，逐渐增大k，当首次得到“是”时，当前k即为最小值。这种办法结合了决策问题的简便性和优化问题的精度。
4.2 决策问题与计数问题
计数问题要求计算某个结构（如哈密顿回路、可满足赋值）的总数，而非仅判断存在性。例如，#SAT（计数可满足赋值数）比SAT更难：SAT的每个实例可被#SAT的计数结果是否为0来判定，因此#SAT至少和SAT一样难。事实上，#P类（多项式时间计数类）中的#SAT是#P完全的，而SAT属于NP。一般来说，计数问题的复杂度往往不低于对应的决策问题，有时候显著更高。
4.3 决策问题与搜索问题
搜索问题要求输出一个具体的解（如一条哈密顿回路、一个可满足赋值），而决策问题仅判断解的存在性。在许多情况下，决策问题可以多项式时间归约到搜索问题：如果能找到解，则解的存在性自然知道。反之，如果决策问题能有效求解，有时也可通过自归约技术（如SAT的求解器输出赋值）来找到解。因此，决策问题和搜索问题的复杂性通常相关联，但并非总是等价（例如，在NP中，如果P=NP，则决策和搜索可互相转换；但在一般函数问题中，搜索可能更难）。
5 历史与代表人物
5.1 希尔伯特第十问题
1900年，大卫·希尔伯特在巴黎国际数学家大会上提出了23个问题，其中第十问题要求设计一个算法，判定任意丢番图方程（整系数多项式方程）是否存在整数解。1970年，尤里·马蒂亚塞维奇基于马丁·戴维斯、希尔普特·罗宾逊等人的工作，证明该问题不可判定。这一结果标志着数论中一个基本问题的算法不可解性，并推动了不可判定性理论的发展。
5.2 图灵与不可判定性
阿兰·图灵于1936年发表《论可计算数及其在判定问题上的应用》，引入图灵机模型，并证明了停机问题的不可判定性。他的工作不仅奠基了计算理论，还通过归约方法证明了多个数学问题的不可判定性。图灵的论证表明，任何足够强的形式系统都存在无法证明的真命题，这本质上与哥德尔不完备定理一脉相承。
5.3 库克与NP完全性理论
斯蒂芬·库克在1971年的论文《定理证明过程的复杂度》中提出了NP完全性的概念，并证明了SAT是NP完全的。此后，理查德·卡普在1972年通过21个问题的归约，展示了NP完全性的广泛存在。库克的工作为计算复杂性理论设立了核心框架，促使科学家理解许多自然问题的“硬核”本质。NP完全性理论成为计算机科学中区分“易解”与“难解”问题的标准工具。
6 应用与意义
6.1 算法设计与分析
决策问题的分类直接指导算法设计：对于P类问题，可以寻求多项式时间精确算法；对于NP完全问题，通常放弃精确解法，转而采用近似算法、启发式或参数化算法。决策问题还用于评估算法复杂度的下界，例如通过规约证明问题至少与某个已知困难问题一样难。SAT求解器的高效性使得工程实践中大量NP困难问题能够通过编码为SAT后求解。
6.2 软件验证与形式化方法
在模型检验中，系统的正确性常被转化为某种决策问题（如时序逻辑的可满足性、自动机语言包含问题）。例如，判断一个有限状态系统是否满足给定的线性时序逻辑性质，即LTL模型检验，可在多项式空间内完成。软件验证中的符号执行、抽象解释等技术，也依赖各种决策过程的可判定性（如线性算术理论、位向量理论的SMT求解器）。决策问题的可判定性边界决定了形式化方法适用于哪一类系统。
6.3 人工智能与约束满足
人工智能中的约束满足问题（CSP）本质上是一类广泛决策问题：给定一组变量、值域和约束，判断是否存在满足所有约束的赋值。CSP的决策版本在规划、调度、配置、自然语言理解中均有应用。许多推理任务（如贝叶斯网络的推理）可归约为#SAT或其他计数决策问题。此外，自动定理证明、逻辑程序设计等基础领域直接以决策问题为核心——归结法试图判断子句集是否可满足，而SMT求解器综合处理多个理论的可满足性。决策问题的理论成果为智能系统的推理引擎提供了数学基础。