一个问题，它既是 NP (可在非确定性多项式时间内验证) 又是 NP-难 (任何 NP 问题都可以转化为这个问题)。NP-难问题的例子包括哈密顿回路和旅行商问题。
在一篇里程碑式的论文中，Karp (1972) 表明 21 个难解的组合计算问题都是 NP 完全问题。
NP完全问题
另请参阅
图同构完备, 哈密顿回路, NP-难问题, NP 问题, P 问题, P 与 NP 问题, 旅行商问题使用 Wolfram|Alpha 探索
参考文献
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.在 Wolfram|Alpha 中被引用
NP完全问题请引用为
Weisstein, Eric W. "NP-完全问题。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/NP-CompleteProblem.html