NP、NP完全与NP难问题列表验证及权威资源请求

先明确核心定义：

• NP问题：能在多项式时间内验证一个解是否正确的问题，所有NP完全问题都属于NP，但NP问题不一定是NP完全。
• NP完全问题：属于NP范畴，且所有NP问题都能通过多项式时间归约转化为该问题。
• NP难问题：所有NP问题都能通过多项式时间归约转化为该问题，但该问题本身不一定属于NP（比如部分不可判定问题）。

原列表存在的核心问题是未区分问题的判定版本和优化版本，以及部分分类不准确，以下是修正后的分类：

一、NP问题 #

• 哈密顿路径问题
• 子集和问题（判定版本：是否存在子集和为目标值）
• 图同构问题（注：目前未被证明为NP完全，属于NP但暂归为NP中间问题，假设P≠NP）
• 布尔可满足性问题（SAT，判定版本：是否存在赋值使公式为真）
• 顶点覆盖问题（判定版本：是否存在大小为k的顶点覆盖）
• 0-1背包问题（判定版本：是否存在总重量≤容量且总价值≥目标值的方案）
• 3-SAT问题
• 团问题（判定版本：是否存在大小为k的团）
• 旅行商问题（TSP，判定版本：是否存在总权重≤k的回路）
• 最大独立集问题（判定版本：是否存在大小为k的独立集）

二、NP完全问题 #

• 布尔可满足性问题（SAT）
• 旅行商问题（TSP，判定版本）
• 0-1背包问题（判定版本）
• 图着色问题（判定版本：是否存在k种颜色合法着色图）
• 哈密顿回路问题
• 子集和问题（判定版本）
• 3-SAT问题
• 斯坦纳树问题（判定版本：是否存在总权重≤k的斯坦纳树）
• 装箱问题（判定版本：是否能用k个箱子装完所有物品）
• 车辆路径问题（VRP，判定版本：是否存在总路程≤k的配送路径）

三、NP难问题 #

• 停机问题（不可判定问题，不属于NP）
• 波斯特对应问题（不可判定问题，不属于NP）
• 0-1背包问题（优化版本：求总价值最大的背包方案）
• 图着色问题（优化版本：求最少需要的着色数）
• 哈密顿回路问题（注：若指寻找所有哈密顿回路等非判定任务，属于NP难；判定版本为NP完全）
• 斯坦纳树问题（优化版本：求总权重最小的斯坦纳树）
• 装箱问题（优化版本：求最少需要的箱子数）
• 顶点覆盖问题（优化版本：求最小大小的顶点覆盖）
• 独立集问题（优化版本：求最大大小的独立集）
• 划分问题（优化版本：求最接近均等的划分方案；判定版本为NP完全）

原列表的主要错误点 #

1. 未区分判定/优化版本：比如背包问题、TSP等，判定版本属于NP/NP完全，优化版本属于NP难，原列表直接重复归类导致混淆。
2. 图同构问题：原列表将其归为NP问题是对的，但它不是NP完全问题（目前无证明）。
3. 顶点覆盖、最大独立集、团问题：它们的判定版本属于NP完全（因此也属于NP），原列表在NP和NP难中重复出现的原因是未区分版本。

内容的提问来源于stack exchange，提问作者jaykio77