一個問題，它既是 NP (可在非確定性多項式時間內驗證) 又是 NP-難 (任何 NP 問題都可以轉化為這個問題)。NP-難問題的例子包括哈密頓迴路和旅行商問題。
在一篇里程碑式的論文中，Karp (1972) 表明 21 個難解的組合計算問題都是 NP 完全問題。
NP完全問題
另請參閱
圖同構完備, 哈密頓迴路, NP-難問題, NP 問題, P 問題, P 與 NP 問題, 旅行商問題使用 探索
參考文獻
Buckley, F. and Harary, F. 圖的距離。 Redwood City, CA: Addison-Wesley, 1990.Garey, M. R. and Johnson, D. S. 計算機和難解性：NP-完全性理論指南。 New York: W. H. Freeman, 1983.Karp, R. M. "組合問題之間的可歸約性。" In 計算機計算的複雜性，IBM Thomas J. Watson 研究中心研討會論文集，紐約州約克鎮高地，1972 年 (Ed. R. E. Miller and J. W. Thatcher). New York: Plenum, pp. 85-103, 1972.Levin, L. A. "通用搜索問題。" Prob. Info. Transm. 9, 265-266, 1973.Papadimitriou, C. H. and Steiglitz, K. 組合最佳化：演算法與複雜度。 New York: Dover, 1998.在 中被引用
NP完全問題請引用為
Weisstein, Eric W. "NP-完全問題。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/NP-CompleteProblem.html