NP-complete问题列表

非决定性多项式集合完备问题列表（NP完备问题列表）列出了一些较常见的NP完备问题。此类问题数以千计，因此本列表只列出一些较常见的和大众文化中较为知名的。著作收录了许多这类问题。

## 图与超图

图经常出现在日常应用中。例如生物网络或社交网络，在某些情况下包含数百、数千甚至数十亿个节点（例如Facebook或LinkedIn）。

- 1-平面性
- 三维匹配问题
- 带宽问题
- 二分维度
- 有容受限制的最小生成树
- 针对混合图（同时具有有向和无向边）的中国邮递员问题（Route inspection problem）。如果图全是无向边或全是有向边，则该程序可在多项式时间内求解。变体包括乡村邮递员问题（rural postman problem）。
- 分团覆盖问题
- 分团问题
- 完全着色，又称消色数（achromatic number）
- 圈秩
- 度受限生成树
- 控制数
- 支配集，又称支配数（domination number）

NP完全的特例包括边支配集问题，即线图中的支配集问题。NP完全的变体包括连通支配集问题和最大叶生成树问题。

- 反馈顶点集
- 反馈弧集
- 图着色问题
- 图同态问题
- 将图划分为特定类型的子图（三角形、同构子图、哈密顿子图、森林、完美匹配）已知是NP完全的。划分为分团（cliques）与对给定图的补图进行着色是同一个问题。一个相关的问题是寻找一个在部分之间的边数方面最优的划分。
- 有向图的Grundy数。
- 哈密顿补完
- 哈密顿路径问题，包括有向和无向。
- 导出子图同构问题
- 图相交数
- 最长路径问题
- 最大二分子图或（特别是带权重的边）最大割问题。
- 最大公共子图同构问题
- 最大独立集
- 最大导出路径
- 最小极大独立集，又称最小独立支配集

NP完全的特例包括最小极大匹配问题，这本质上等同于边支配集问题（见上文）。

- 图的度量维度
- 度量k-中心
- 最小度生成树
- 最小k-割
- 最小k-生成树
- 子式测试（检查输入图 $G$ 是否包含输入图 $H$ 作为子式）；拓扑子式也是如此
- 史坦纳树，或图中顶点子集的最小生成树。（整个图的最小生成树可在多项式时间内求解。）
- 模组度最大化
- 单色三角形
- 路径宽度，或等价的区间厚度（interval thickness）和顶点分离数（vertex separation number）
- 秩着色（Rank coloring）
- k-中国邮递员问题
- 最短总路径长生成树
- 斜率数为2的测试
- 识别弦图 (String graph)
- 子图同构问题
- 树宽
- 测试一棵树是否可以表示为欧几里得最小生成树
- 顶点覆盖

## 数学规划

- 3-划分问题
- 装箱问题
- 瓶颈旅行推销员问题
- 无容量限制的设施选址问题
- 流水线调度
- 广义指派问题
- 整数规划。变数被要求为0或1的变体，称为0-1线性规划，以及其他几个变体也是NP完全的
- 与作业车间调度相关的一些问题
- 背包问题、二次背包问题以及几个变体
- 与多处理机调度相关的一些问题
- 数值三维匹配
- 开放车间调度
- 划分问题
- 二次指派问题
- 二次规划（某些情况下是NP困难的，如果为凸则是P）
- 子集和问题
- 旅行推销员问题的变体。如果假设边长为整数，则图的该问题是NP完全的。平面上点的问题在离散欧几里得度量和直线度量下是NP完全的。已知该问题在（非离散）欧几里得度量下是NP困难的。

## 形式语言与字串处理

- 最近字串
- 多个序列的最长公共子序列问题
- 波斯特对应问题的有界变体
- 多个序列的最短公共超序列
- 字串到字串校正问题的扩展

## 游戏与智力游戏

- Bag (Corral)
- 海战棋
- 1A2B，市面上称为珠玑妙算（Master Mind）：某些优化问题是，但游戏本身不是。
- 边缘匹配拼图
- 填骨牌
- （广义）新接龙
- 碁石拾
- 数桥
- 汉雅和绘
- （广义）疯狂的方块（Instant Insanity）
- 数和（Kakuro）
- 多米诺王国
- 黑白方阵（也称为Kurodoko）
- LaserTank
- 百战小旅鼠（在多项式时间限制下）
- 美术馆（Light Up）
- 麻将接龙（可以看见牌堆下方的牌）
- 珍珠（Masyu）
- 踩地雷一致性问题（参见 Scott, Stege, & van Rooij）
- 数织
- 数连
- 数墙
- （广义）瘟疫危机
- 孔明棋
- n-皇后补完
- N×N×N 魔方的最优解
- SameGame
- Shakashaka
- 多种网格上的数回
- （广义）数独
- 叠榻米
- 天体秀
- 与俄罗斯方块相关的问题
- 覆面算

## 其他

- 泊位分配问题
- 介数问题
- 组装一个最优的比特币区块。
- 布尔可满足性问题（SAT）。还有许多变体也是NP完全的。一个重要的变体是每个子句恰好有三个文字（3SAT），因为它被用于许多其他NP完全性结果的证明。
- 电路可满足性问题
- 合取布尔查询
- 循环排序
- 精确覆盖问题。对于3-集仍然是NP完全的。对于2-集可在多项式时间内求解（这是一个匹配）。
- 寻找哈特里-福克方程的全域最小解
- 向上平面性（Upward planarity）测试
- 医院与住院医师问题（Hospitals-and-residents problem with couples）
- 结亏格
- 拉丁方阵补完（确定部分填充的方阵是否可以完成的问题）
- 最大2-可满足性
- 最大体积子矩阵 – 从较大的 $m\times n$ 矩阵中选择条件最好的子集的问题。此类问题与秩揭示QR分解和D最优实验设计有关。
- 序列的最小加法链。单个数字的最小加法链的复杂度未知。
- 模态逻辑 S5-可满足性
- 字串的煎饼排序距离问题
- 整数上双变数二次多项式的可解性。给定正整数 $\textstyle A,B,C$，判定是否存在正整数 $x,y$ 使得 $Ax^2+By-C=0$
- 根据同一篇文章，具有任意合数模数的有界模平方根的存在性。给定正整数 $\textstyle A,B,C \geq 0$，判定是否存在整数 $x\in[0,C]$ 使得 $x^2\equiv A\bmod B$。即使提供了 $B$ 的质因数分解，该问题仍然是NP完全的。
- 数据库历史的可序列化
- 集合覆盖问题（也称为“最小覆盖”问题）。透过转置关联矩阵，这等同于撞击集（hitting set）问题。
- 集合包装（Set packing）
- 集合分割问题
- 最小化加权完成时间的调度
- 块排序（Block Sorting）（透过块移动排序）
- 稀疏逼近
- 史坦纳树问题的变体。具体来说，具有离散欧几里得度量、直线度量。已知在（非离散）欧几里得度量下，该问题是NP困难的。
- 三维易辛模型

## 参考文献

### 综合

- . This book is a classic, developing the theory, then cataloguing many NP-Complete problems.

### 具体

- Further information available online at Richard Kaye's Minesweeper pages .

## 外部链接

- A compendium of NP optimization problems
- Graph of NP-complete Problems