1 基本概念
NP完全性研究的核心，是把“可快速验证”与“同类中最难”这两个性质结合起来考察。它通常针对决策问题，即答案只有“是”或“否”的问题，并通过多项式时间归约来比较问题之间的难度。
1.1 NP 类问题
NP类问题指的是这样一类决策问题：如果某个实例的答案为“是”，那么可以借助一个简短证明或证书，在多项式时间内验证其正确性。这里强调的是验证效率，而不是寻找解的效率。
1.1.1 多项式时间验证
“多项式时间验证”意味着，给定问题实例和一个候选证据后，检验该证据是否成立所需的时间是输入规模的多项式函数。换言之，虽然找到答案可能很难，但一旦有人给出一个声称正确的解，机器可以较快地检查它是否有效。
1.1.2 非确定性图灵机视角
从非确定性图灵机的角度看，NP可以理解为：存在一类计算模型，它能够通过“猜测”某个解并在多项式时间内验证其正确性。若存在至少一条计算分支能够接受输入，则该输入被判定为“是”。这一视角为NP类的形式化定义提供了重要基础。
1.2 多项式时间归约
多项式时间归约是一种比较问题难度的方法。若能把问题A在多项式时间内转化为问题B，并保证B的解可以回答A的原问题，那么B至少不比A简单。归约是NP完全性理论中的关键工具。
1.2.1 归约的定义
若存在一个多项式时间可计算的映射，将任意输入实例从问题A转换为问题B的实例，并使得转换前后“是/否”答案保持一致，则称A可多项式归约到B。记作 A ≤p B。这表明，B能够“模拟”A的难度。
1.2.2 归约的传递性
多项式时间归约具有传递性：如果 A ≤p B，且 B ≤p C，那么 A ≤p C。这个性质使得归约链可以层层传递，也使得一旦某个问题被证明为难题，它的难度可以沿着归约网络扩散到更多问题。
1.3 NP 完全问题的定义
NP完全问题是NP类中最具代表性的难问题。它既要求问题本身可在多项式时间内验证，又要求所有NP问题都能归约到它。直观上，它是NP中的“难度天花板”。
1.3.1 属于 NP
一个问题要成为NP完全问题，首先必须属于NP。也就是说，若该问题的答案为“是”，则存在一个可在多项式时间内检查的证书，能够证明答案正确。
1.3.2 NP 困难性
除了属于NP之外，它还必须满足NP困难性：任意NP问题都能在多项式时间内归约到它。这个条件说明，它至少和NP中的任何问题一样难。
1.3.3 NP 完全与 NP 困难的区别
NP完全问题一定属于NP，而NP困难问题不一定属于NP。前者兼具“可验证”与“最难”双重性质，后者只要求难度足够高，未必有多项式时间验证证书。有些优化问题的版本常被归为NP困难，但其决策形式才可能是NP完全。
2 理论背景
NP完全性并不是孤立概念，而是建立在计算复杂性理论的整体框架之上。它与时间、空间、可计算性和计算模型等基础概念密切相连。
2.1 计算复杂性理论
计算复杂性理论研究的是问题在资源受限条件下的求解难度，特别关注时间和空间消耗。NP完全性是其中最著名的分类结果之一。
2.1.1 决策问题与判定问题
决策问题也常被称为判定问题，指的是答案只能取“是”或“否”的问题。例如“图中是否存在哈密顿回路”就是一个典型的决策问题。许多实际问题在进入复杂性分析时，都会被转化为这种形式。
2.1.2 时间复杂度与空间复杂度
时间复杂度描述算法运行所需步骤数，空间复杂度描述所需存储量。NP完全性主要讨论的是时间资源，尤其是多项式时间与指数时间之间的差异。
2.2 P、NP 与 co-NP
P、NP和co-NP是复杂性理论中最基础的一组类别，它们分别从可求解、可验证以及“否定实例的可验证性”角度刻画问题。
2.2.1 P 类问题
P类问题是能够在多项式时间内被确定性算法直接求解的问题。它代表通常意义下“高效可解”的问题集合。
2.2.2 NP 类问题
NP类问题则强调“正例可验证”。它不保证能快速求解，但若答案为“是”，则可以较快确认。NP完全问题正是NP中的极端代表。
2.2.3 P 与 NP 问题
P与NP的关系是计算复杂性中最著名的问题之一。已知 P 包含于 NP，但是否相等仍未解决。若二者相等，则许多目前看来难以求解的问题都可能存在多项式时间算法；若不相等，则NP中存在本质上更难的问题。
2.3 非确定性计算模型
非确定性计算模型为NP的定义提供了直观基础。它并不表示现实中真的存在某种“神秘机器”，而是一种用于刻画计算能力的抽象工具。
2.3.1 非确定性图灵机
非确定性图灵机可以在某一步同时“尝试”多个选择分支。只要其中一条分支在多项式时间内接受输入，整个输入就被接受。这种模型与NP类的定义在形式上是等价的。
2.3.2 证书与验证器
证书是用来证明答案为“是”的辅助信息，验证器则是检查证书是否正确的算法。若存在一个多项式时间验证器，能够对任意输入及其证书进行验证，那么该问题通常可归入NP。
3 NP 完全性的核心定理
NP完全性理论之所以成立，关键在于若干基础定理与证明框架。其中最著名的是Cook-莱文定理，它首次证明了一个具体问题是NP完全的。
3.1 Cook-莱文定理
Cook-莱文定理指出，布尔可满足性问题是第一个被证明为NP完全的问题。这一结果奠定了整个NP完全性理论的起点。
3.1.1 第一个 NP 完全问题
在Cook-莱文定理之前，虽然人们已经观察到一些问题很难，但缺少统一的“最难”标准。该定理表明，SAT不仅属于NP，而且NP中的任意问题都能归约到它，因此它成为第一个公认的NP完全问题。
3.1.2 布尔可满足性问题（SAT）
SAT要求判断一个布尔公式是否存在一组变量赋值，使公式为真。它是逻辑与计算复杂性之间的经典桥梁，也因此成为大量归约的起点。
3.2 归约链与完备性证明
证明一个新问题NP完全，通常要借助已有的NP完全问题作为“源头”，沿着归约链逐步转化。这样的证明思路既系统又具有可复用性。
3.2.1 从已知 NP 完全问题归约
常见做法是从SAT、3-SAT或某个经典图问题出发，把它转换为待证明问题。若转换过程保持答案一致，并且转换可在多项式时间完成，就能证明目标问题至少同样困难。
3.2.2 证明新问题 NP 完全的标准流程
标准流程通常包括两步：先证明目标问题属于NP，再从一个已知NP完全问题出发构造多项式归约。两步都完成后，便可断定该问题是NP完全的。
3.3 常见证明技巧
NP完全性证明往往依赖巧妙的构造。不同问题之间看似差异很大，但归约时常通过编码、结构模拟和约束设计建立对应关系。
3.3.1 构造性归约
构造性归约强调显式建立实例之间的映射，而不是仅作抽象说明。证明者需要清楚说明，原问题中的每个元素如何在目标问题中被模拟。
3.3.2 伪装成优化问题的决策化处理
很多实际问题先以优化形式出现，例如“求最短路径”或“使成本最低”。在复杂性理论中，往往先将其转写为决策版，例如“是否存在成本不超过K的解”，从而进入NP完全性分析框架。
3.3.3 编码与约束表达
归约时常把逻辑公式、集合关系或图结构编码为目标问题中的对象。通过设计约束，使得合法解与原问题解一一对应，是NP完全性证明中常见的技术路线。
4 经典 NP 完全问题
NP完全问题种类很多，涉及逻辑、图论、组合优化等多个领域。以下问题大多已成为复杂性理论中的经典样本。
4.1 布尔逻辑相关问题
布尔逻辑类问题通常是NP完全性理论的起点，因为它们天然适合用公式、变量和赋值来描述。
4.1.1 SAT
SAT是判断布尔公式是否可满足的问题。作为第一个NP完全问题，它在理论和应用中都具有基础地位。
4.1.2 3-SAT
3-SAT是SAT的限制版本，每个子句恰有三个文字。尽管形式更受限，它仍然是NP完全的，因此常作为其他NP完全性证明的出发点。
4.1.3 CNF-SAT
CNF-SAT指判断合取范式公式是否可满足。由于合取范式结构清晰、便于处理，它在很多归约中都比一般SAT更易使用。
4.2 图论问题
图论提供了大量直观且结构化的NP完全问题。许多问题可通过节点、边和颜色等对象表达，便于构造归约。
4.2.1 哈密顿回路问题
哈密顿回路问题要求判断图中是否存在一条经过每个顶点恰好一次并回到起点的回路。它看上去很自然，却是经典NP完全问题之一。
4.2.2 顶点覆盖问题
顶点覆盖问题询问是否存在一个大小不超过k的顶点集合，使每条边至少有一个端点落在该集合中。它常与独立集、团问题相互关联。
4.2.3 团问题
团问题要求判断图中是否存在大小为k的完全子图。由于团在图结构中代表高度密集的连接模式，该问题在网络分析和理论证明中都很常见。
4.2.4 图着色问题
图着色问题询问是否能用不超过k种颜色为顶点着色，使相邻顶点颜色不同。它既具有直观性，也与调度、资源分配等应用场景紧密相关。
4.2.5 独立集问题
独立集问题判断图中是否存在大小为k的顶点集合，使集合内任意两点之间都没有边相连。它与顶点覆盖在很多性质上互为对应。
4.3 数学与组合优化问题
除了逻辑和图论，许多数值与组合问题也属于NP完全或NP困难。它们往往来自最优化背景，但在决策化后具有明确的复杂性分类。
4.3.1 子集和问题
子集和问题要求从一组整数中选出若干个，使其和等于指定目标值。它是经典的数值型NP完全问题，结构简洁而用途广泛。
4.3.2 背包问题
背包问题通常问：在容量限制下，是否能选取若干物品，使总价值达到某个阈值。其决策版本是NP完全的，而优化版本则常被视为NP困难。
4.3.3 旅行商问题（决策版）
旅行商问题的决策版询问是否存在一条总长度不超过给定界限的巡回路线。它在优化、路径规划和运筹学中都极具代表性。
4.3.4 划分问题
划分问题要求把一组数分成两部分，使两部分和相等或尽量平衡。它与子集和问题联系紧密，也是常见的组合复杂度例题。
5 证明方法与归约策略
NP完全性证明并不只依赖单一模板，而是形成了一整套归约策略。理解这些方法，有助于识别问题之间的结构对应关系。
5.1 从 SAT 出发的归约
SAT及其限制版本因表达能力强，常被用作证明其他问题NP完全的起点。许多归约都会先把逻辑约束转成目标问题中的结构。
5.1.1 3-SAT 到图问题
3-SAT到图问题的归约十分常见，例如将变量、子句和满足关系编码为图的顶点和边。通过这种映射，可以把逻辑可满足性转化为图结构是否存在特定模式的问题。
5.1.2 逻辑公式到组合结构的映射
归约中常把公式中的“或”“与”“非”关系映射为组合结构中的选择、连接或排斥条件。只要设计得当，公式的满足性就能对应到目标结构的可行性。
5.2 从图问题到其他问题
图问题往往具有较强的结构直观性，因此也常被用来向其他问题归约。其优势在于边、点和路径等元素容易转换成资源、约束和状态。
5.2.1 路径与回路类归约
路径和回路类问题通常可转换为是否存在某种遍历、访问或闭合结构。通过控制访问顺序与重复限制，可以把图中的路径性质嵌入到新的问题模型中。
5.2.2 着色与覆盖类归约
着色问题与覆盖问题经常作为中介问题使用。它们能够把“冲突避免”或“选择最少代表”的需求，转化为某种可验证的组合配置。
5.3 常见归约陷阱
归约证明看似直接，实际却容易出现细节错误。许多证明失败并非因为思路错误，而是因为映射没有完整保持问题本质。
5.3.1 保持“是/否”答案一致
归约的首要要求，是转换前后的答案必须严格对应。若某些“否”实例被错误映射成“是”实例，证明就会失效。
5.3.2 多项式时间可构造性
即便映射逻辑正确，如果构造目标实例的过程本身过慢，也不能称为多项式归约。因而构造步骤的时间复杂度必须受到严格控制。
5.3.3 输入规模控制
归约时还要注意实例规模不能失控增长。若输出规模指数级膨胀，哪怕答案对应正确，也不满足多项式时间归约的要求。
6 NP 完全性的意义与影响
NP完全性之所以重要，不只是因为它给出了一类难题的标签，更因为它改变了人们理解算法与问题难度的方式。
6.1 算法设计中的作用
在算法设计中，识别某个问题是否NP完全，往往能帮助研究者判断是否应继续寻找精确多项式算法，还是转向近似、随机化或特定参数情形。
6.1.1 识别难题边界
一旦问题被证明为NP完全，通常意味着它不太可能存在普适的高效精确算法。这为算法开发提供了明确的难度边界。
6.1.2 促使寻找近似算法
面对NP完全问题，人们常转而研究近似解，即用较少资源得到质量可接受的结果。近似算法因此成为处理困难问题的重要方向。
6.1.3 促使寻找参数化算法
参数化算法关注某些关键参数较小时的可解性。即使整体问题是NP完全的，在参数受限时仍可能获得高效求解，这为实际应用提供了更多空间。
6.2 复杂性理论中的地位
NP完全性不仅是一个分类结论，也是连接复杂性理论多个分支的枢纽。它把逻辑、图论、优化与可计算性联系在一起。
6.2.1 作为“难度基准”
NP完全问题常被当作难度基准，用来衡量新问题的计算复杂度。若一个问题能归约到已知NP完全问题，便可推断它至少同样困难。
6.2.2 连接多个子领域
从布尔逻辑到图算法，再到组合优化，NP完全性理论在多个学科方向之间建立了共通语言。它使不同领域的问题可以在统一框架下比较。
6.3 对实际问题建模的启发
现实中的很多资源受限问题都能抽象成NP完全或NP困难模型。尽管理论上很难，这种抽象却有助于理解问题结构并选择合适策略。
6.3.1 调度问题
调度问题常涉及任务排序、机器分配和时间冲突。很多版本可被建模为图着色、覆盖或约束满足问题，因此与NP完全性联系紧密。
6.3.2 网络设计问题
网络设计中常见连通性、路径选择和容错要求。若要求在复杂约束下满足最优或可行条件，相关模型往往会呈现NP完全特征。
6.3.3 资源分配问题
资源分配问题关注如何在有限条件下最大化收益或满足需求。其决策版常能自然转写为子集选择、划分或背包类型问题。
7 相关概念与扩展
NP完全性并不是复杂性理论的终点。围绕它，还形成了NP困难、PSPACE、近似计算和随机化等一系列相关概念。
7.1 NP 困难问题
NP困难问题表示至少与NP中最难的问题一样难，但不一定具有NP所要求的可验证性。这一概念扩展了“困难”这一判断的范围。
7.1.1 与 NP 完全问题的关系
NP完全问题是NP困难问题中的特殊子类：既要足够难，又必须属于NP。可以说，NP完全性是NP困难性的“可验证版本”。
7.1.2 不属于 NP 的 NP 困难问题
有些问题可能比NP完全问题还难，甚至根本不满足NP的验证要求。例如某些优化问题或更高层级问题，常被归为NP困难，但不能直接称为NP完全。
7.2 PSPACE 与更高复杂度类
除了NP及其相关概念，复杂性理论还研究需要更多空间资源的问题。PSPACE是其中一个重要类别。
7.2.1 多项式空间问题
PSPACE类问题指可以使用多项式空间解决的问题。它与NP不同，关注的是内存占用而非验证证书，因而刻画了另一种复杂度维度。
7.2.2 完全性层级
在更高复杂度类中，也存在对应的“完全”概念，如PSPACE完全问题。它们与NP完全问题类似，都是各自类别中的最难代表，但所属层级更高。
7.3 近似与随机化视角
当精确求解困难时，近似算法和随机化方法提供了替代路径。它们并不改变问题的最坏情形难度，却能在实际中带来可用解法。
7.3.1 近似可解性
近似可解性研究的是，在允许误差的情况下，问题能否被有效求解，以及误差界限能否被控制。对于很多NP困难问题，这是非常重要的研究方向。
7.3.2 随机化算法与概率验证
随机化算法利用随机选择来提高效率或简化设计。某些问题还可以通过概率验证来检查答案，形成与传统确定性验证不同的框架。
7.3.3 不可近似性结果
除了证明问题难以精确求解，研究者还会讨论它是否难以近似。不可近似性结果说明，即使放宽要求，也可能无法获得任意好的近似解。
8 争议与开放问题
NP完全性理论本身非常成熟，但围绕它仍有许多深层问题未获解决，尤其是P与NP的关系以及理论与实践之间的鸿沟。
8.1 P 是否等于 NP
P是否等于NP是现代计算机科学最著名的开放问题之一。它不仅关乎理论分类，也关系到算法可行性的根本理解。
8.1.1 问题陈述
问题的核心是：凡是答案可在多项式时间内验证的问题，是否也都能在多项式时间内求解。若答案为肯定，则NP中的所有问题都能被高效解决；若否，则存在本质上不可高效求解的问题。
8.1.2 研究现状
目前尚未证明P=NP，也未证明P≠NP。尽管已有大量部分结果和相对结果，主问题仍然悬而未决，并持续吸引理论研究。
8.2 完全性理论的局限
NP完全性提供了强有力的分类工具，但它并不能完整描述现实算法的表现，也不能直接给出实际求解方案。
8.2.1 对实际可解性的解释边界
一个问题被证明为NP完全，并不意味着它在所有实际场景下都难以处理。许多实例可能具有特殊结构，因而可以用启发式或专门算法高效解决。
8.2.2 与工程可行性的差异
工程实践更关注典型输入、近似容忍度和资源限制，而理论复杂性主要看最坏情况。两者关注点不同，因此NP完全性不能简单等同于“不可用”。
8.3 未来研究方向
尽管基础框架已建立多年，NP完全性相关研究仍在继续深化，尤其体现在更细致的分类与证明技术上。
8.3.1 更精细的复杂度分类
未来研究常致力于把“大类难题”进一步细分，寻找更准确的边界条件，例如特殊结构、参数范围或平均情形下的复杂度差异。
8.3.2 证明技术的改进
随着问题越来越复杂，归约与证明方法也在演化。更简洁、更模块化、更适合自动化分析的技术，有助于推动复杂性理论向前发展。