概要

1

P類別是在確定性圖靈機上可以在多項式時間內判定的一類問題，而NP類別是當給定一個結果為Yes的證據（稱為Witness）時，可以在多項式時間內判定Witness正確性（稱為驗證）的一類問題。由於在多項式時間內可判定的問題可以在多項式時間內驗證，因此P⊆NP是顯而易見的，但P是否為NP的真子集仍不清楚。目前尚無證明，但許多研究人員相信P≠NP。而這種認為P類別和NP類別不相等的猜想被稱為「P≠NP猜想」。