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