如果一個問題可以透過非確定型圖靈機在多項式時間內解決，則該問題被歸為 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 問題、
圖靈機
使用 探索
參考文獻
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.在 上被引用
NP-問題
引用為
Weisstein, Eric W. "NP-問題。" 來自 Web 資源。 https://mathworld.tw/NP-Problem.html
主題分類
