NP

參考資料 1：時間複雜性和空間複雜性研究(3張)

NP，即非確定性多項式時間複雜性 Non-deterministic polynomial time 這一複雜度類的縮寫。所謂非確定性，就是指可以同時做出多種選擇並進行相應的計算，而只要在一種選擇中計算結果是真，那麼最終的計算結果就為真。一個便於理解的詮釋是，NP 問題是一類可在多項式時間內驗證你給出的答案是否正確的問題。

NP 相關的問題中一個重要的概念是 NP-complete 問題。如果對於某一個 NP 問題 L, NP 中所有的問題 A 都可以在多項式時間內多一規約 (many-one reduction) 到 L，那麼 L 就是一個 NP-complete 問題 ^[1]  。從定義來説，如果 L 可以被高效地（即在多項式時間內）解決，那麼所有 NP 中的問題都可以被高效地解決，也就是説 L 比 NP 中的所有問題都要“難”。對這個命名的一種理解方式是，這類問題本身就可以作為所有 NP 問題的代表，或者説它們是所有 NP 問題中最難的一部分。所以在研究 NP 與 P 間關係的時候，常見的一個着手點就是對 NP-complete 問題進行分析。

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