非決定性多項式集合完備問題列表（NP完備問題列表）列出了一些較常見的NP完備問題。此類問題數以千計，因此本列表只列出一些較常見的和大眾文化中較為知名的。 的著作收錄了許多這類問題。
圖與超圖
圖經常出現在日常應用中。例如生物網絡或社交網絡，在某些情況下包含數百、數千甚至數十億個節點（例如Facebook或LinkedIn）。
*
*三維匹配問題
*
::NP完全的特例包括最小極大匹配問題，
*
*秩著色（Rank coloring）
*k-中國郵遞員問題
*
*識別
*
*測試一棵樹是否可以表示為
*
*多個序列的最長公共子序列問題
*
*1A2B，市面上稱為珠璣妙算（Master Mind）：某些優化問題是，但遊戲本身不是。
*
*
*（）
*
*數橋
*
*（）瘋狂的方塊（Instant Insanity）
*
*（也稱為Kurodoko）
*
*百戰小旅鼠（在多項式時間限制下）
*美術館（Light Up）
*麻將接龍（可以看見牌堆下方的牌）
*（Masyu）
*踩地雷一致性問題（參見 Scott, Stege, & van Rooij）
*數織
*
*
*（）瘟疫危機
*孔明棋
*n-皇后補完
- 魔方的最優解
*
*
*多種網格上的數迴
*（）數獨
*
*
*與俄羅斯方塊相關的問題
*覆面算
其他
*
*
*組裝一個最優的比特幣區塊。
*布爾可滿足性問題（SAT）。
*精確覆蓋問題。對於3-集仍然是NP完全的。對於2-集可在多項式時間內求解（這是一個匹配）。
*向上平面性（Upward planarity）測試
*拉丁方陣補完（確定部分填充的方陣是否可以完成的問題）
*
*序列的最小加法鏈。 單個數字的最小加法鏈的複雜度未知。
*模態邏輯 S5-可滿足性
*字串的煎餅排序距離問題
*整數上雙變數二次多項式的可解性。 給定正整數 \textstyle A,B,C，判定是否存在正整數 x,y 使得 Ax^2+By-C=0
*根據同一篇文章，（透過塊移動排序）
*
*的變體。具體來說，具有離散歐幾里得度量、直線度量。已知在（非離散）歐幾里得度量下，該問題是NP困難的。
參見
*
- 卡普的二十一個NP-完全問題
*
- 歸約
註釋
參考文獻
綜合
- . This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
*
*
*
*
*
具體
*
*
*
*
- Further information available online at [http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ Richard Kaye's Minesweeper pages] .
*
*
*
*
*
外部連結
- [http://www.csc.kth.se/~viggo/problemlist/ A compendium of NP optimization problems]
- [https://adriann.github.io/npc/npc.html Graph of NP-complete Problems]
评论 (0)