NP(非確定性多項式)

簡介

NP，即非確定性多項式 Non-deterministic polynomial的縮寫。所謂非確定性，就是指可以用一定數量的運算去解決多項式時間內可解決的問題。NP 問題通俗來說是其解的正確性能夠被“很容易檢查”的問題，這裡“很容易檢查”指的是存在一個多項式檢查算法。相應的，若NP中所有問題到某一個問題是圖靈可歸約的，則該問題為NP困難問題（NP-Hard或NPH），反之則為NP完全問題（NP-Complete或NPC）。

NP問題是一類可在多項式時間內驗證你給出的答案是否正確的問題， P問題為NP問題的一個子類。

而NP-完全問題則是一類目前大家認為沒有多項式算法去解決的問題，但是如果你給出了這類問題的一個答案，我可以在多項式時間內驗證給出的答案是否正確。

NP-困難問題指的是至少和NP完全問題一樣難的問題。注意，NP-困難問題有可能比NP完全問題難，但卻不會比它容易。

它們之間的關係：NP完全問題是NP問題的一個子類，它是NP問題中最難的一類問題。NP-困難問題和NP-完全問題有交集，但並不同，它還包含一類比NP完全問題更難的問題。

有關猜想

克雷數學研究所懸賞給出的21世紀七大數學猜想，其中有一個問題即為 P與NP問題的等價問題。