如果一个问题可以通过非确定型图灵机在多项式时间内解决，则该问题被归为 NP（非确定性多项式时间）类。
P 问题（其求解时间受多项式限制）始终也是 NP。如果一个问题已知为 NP，并且某种程度上已知该问题的解，那么证明解的正确性始终可以简化为单个 P（多项式时间）验证。如果 P 和 NP 不等价，那么 NP 问题的解（在最坏的情况下）需要穷举搜索。
长期以来已知线性规划为 NP，并被认为不是 P，但在 1979 年被 L. Khachian 证明为 P。确定所有表面上是 NP 问题的问题是否实际上是 P，这是一个重要的未解问题。
如果解决一个问题的算法可以转化为解决任何其他 NP 问题的算法，则称该问题为 NP-难问题。证明一个问题是 NP 比证明它是 NP-难问题容易得多。既是 NP 又是 NP-难的问题称为 NP-完全问题。
参见
复杂度理论、
穷举搜索、
非确定型图灵机、
NP-完全问题、
NP-难问题、
P 问题、
P 对 NP 问题、
图灵机
使用 Wolfram|Alpha 探索
参考文献
Borwein, J. M. 和 Borwein, P. B. Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987.Clay Mathematics Institute. "P vs. NP." http://www.claymath.org/millennium/P_vs_NP/.Cook, S. "The P versus NP Problem." http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf.Crescenzi, P. 和 Kann, V. (Eds.). "A Compendium of NP Optimization Problems." http://www.nada.kth.se/~viggo/wwwcompendium/wwwcompendium.html.Greenlaw, R.; Hoover, H. J.; 和 Ruzzo, W. L. Limits to Parallel Computation: P-Completeness Theory. Oxford, England: Oxford University Press, 1995.Smale, S. "Mathematical Problems for the Next Century." Math. Intelligencer 20, No. 2, 7-15, 1998.Smale, S. "Mathematical Problems for the Next Century." In Mathematics: Frontiers and Perspectives 2000 (Ed. V. Arnold, M. Atiyah, P. Lax, 和 B. Mazur). Providence, RI: Amer. Math. Soc., 2000.在 Wolfram|Alpha 上被引用
NP-问题
引用为
Weisstein, Eric W. "NP-问题。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/NP-Problem.html
主题分类
