NP-complete問題列表

非決定性多項式集合完備問題列表（NP完備問題列表）列出了一些較常見的NP完備問題。此類問題數以千計，因此本列表只列出一些較常見的和大眾文化中較為知名的。 的著作收錄了許多這類問題。

 圖與超圖 
圖經常出現在日常應用中。例如生物網絡或社交網絡，在某些情況下包含數百、數千甚至數十億個節點（例如Facebook或LinkedIn）。

三維匹配問題

針對混合圖（同時具有有向和無向邊）的中國郵遞員問題（Route inspection problem）。如果圖全是無向邊或全是有向邊，則該程序可在多項式時間內求解。變體包括鄉村郵遞員問題（rural postman problem）。
分團覆蓋問題
分團問題
，又稱消色數（achromatic number）

，又稱支配數（domination number）
NP完全的特例包括問題，即線圖中的支配集問題。NP完全的變體包括連通支配集問題和問題。

圖著色問題
圖同態問題
將圖為特定類型的子圖（三角形、同構子圖、哈密頓子圖、森林、）已知是NP完全的。劃分為分團（cliques）與對給定圖的補圖進行著色是同一個問題。一個相關的問題是尋找一個在部分之間的邊數方面最優的劃分。
有向圖的。

哈密頓路徑問題，包括有向和無向。

最長路徑問題
最大二分子圖或（特別是帶權重的邊）最大割問題。

最大獨立集
最大
，又稱最小獨立支配集
NP完全的特例包括最小極大匹配問題，這本質上等同於問題（見上文）。
圖的

子式測試（檢查輸入圖  是否包含輸入圖  作為子式）；拓撲子式也是如此
，或圖中頂點子集的最小生成樹。（整個圖的最小生成樹可在多項式時間內求解。）
模組度最大化

路徑寬度，或等價的區間厚度（interval thickness）和頂點分離數（vertex separation number）; ; .
秩著色（Rank coloring）
k-中國郵遞員問題

為2的測試
識別

樹寬
測試一棵樹是否可以表示為

 數學規劃 

裝箱問題

流水線調度

整數規劃。變數被要求為0或1的變體，稱為0-1線性規劃，以及其他幾個變體也是NP完全的
與相關的一些問題
背包問題、以及幾個變體
與多處理機調度相關的一些問題

開放車間調度
劃分問題

二次規劃（某些情況下是NP困難的，如果為凸則是P）
子集和問題
旅行推銷員問題的變體。如果假設邊長為整數，則圖的該問題是NP完全的。平面上點的問題在離散歐幾里得度量和直線度量下是NP完全的。已知該問題在（非離散）歐幾里得度量下是NP困難的。

 形式語言與字串處理 

多個序列的最長公共子序列問題
波斯特對應問題的有界變體
多個序列的
的擴展

 遊戲與智力遊戲 

1A2B，市面上稱為珠璣妙算（Master Mind）：某些優化問題是，但遊戲本身不是。

（）Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003.

數橋

（）瘋狂的方塊（Instant Insanity）
數和（Kakuro）

（也稱為Kurodoko）

百戰小旅鼠（在多項式時間限制下）
美術館（Light Up）Light Up is NP-Complete
麻將接龍（可以看見牌堆下方的牌）
（Masyu）
踩地雷一致性問題（參見 Scott, Stege, & van RooijAllan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, The Mathematical Intelligencer 33:4 (2011), pp. 5–17.）
數織

（）瘟疫危機
孔明棋
n-皇后補完
 魔方的最優解

多種網格上的數迴
（）數獨A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf) 

與俄羅斯方塊相關的問題
覆面算

 其他 

組裝一個最優的比特幣區塊。
布爾可滿足性問題（SAT）。 還有許多變體也是NP完全的。一個重要的變體是每個子句恰好有三個文字（3SAT），因為它被用於許多其他NP完全性結果的證明。

精確覆蓋問題。對於3-集仍然是NP完全的。對於2-集可在多項式時間內求解（這是一個匹配）。
尋找哈特里-福克方程的全域最小解
向上平面性（Upward planarity）測試
（Hospitals-and-residents problem with couples）

拉丁方陣補完（確定部分填充的方陣是否可以完成的問題）

最大體積子矩陣 – 從較大的  矩陣中選擇條件最好的子集的問題。此類問題與秩揭示QR分解和D最優實驗設計有關。
序列的最小加法鏈。Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981 單個數字的最小加法鏈的複雜度未知。
模態邏輯 S5-可滿足性
字串的煎餅排序距離問題
整數上雙變數二次多項式的可解性。 給定正整數 ，判定是否存在正整數  使得 
根據同一篇文章， 具有任意合數模數的有界的存在性。給定正整數 ，判定是否存在整數  使得 。即使提供了  的質因數分解，該問題仍然是NP完全的。
資料庫歷史的
集合覆蓋問題（也稱為「最小覆蓋」問題）。透過轉置關聯矩陣，這等同於撞擊集（hitting set）問題。
集合包裝（Set packing）
問題
最小化加權完成時間的調度
塊排序（Block Sorting）（透過塊移動排序）

的變體。具體來說，具有離散歐幾里得度量、直線度量。已知在（非離散）歐幾里得度量下，該問題是NP困難的。
三維易辛模型, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

 參見 

 卡普的二十一個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 

Category:數學列表
表
Category:Lists of problems