P 包含於 NP（P is contained in NP）

如果你能快速「求解」一個問題，你當然也能快速「檢查」它的答案：自己解一遍再比對即可。這句一行的觀察，就是「P 中每個問題也屬於 NP」的全部理由。求解至少和檢查一樣好，所以可高效求解的問題坐落在可高效檢查的問題之內。用子集符號 ⊆（包含於）寫成：P ⊆ NP。

把證明放慢來看。取任一屬於 P 的問題；依定義它有一個確定型演算法 A，在多項式時間內執行並輸出正確的是非答案。要證明它屬於 NP，我們必須給出一個多項式時間的驗證器。就用這個：完全忽略證書，在輸入上執行 A，當 A 說「是」時才接受。對「是」實例，「任何」證書（連空字串都行）都管用，所以證書存在；對「否」實例，A 不論如何都說「否」，所以沒有證書管用。由於 A 是多項式時間，驗證器也是。因此該問題屬於 NP，而既然問題是任取的，整個 P 都屬於 NP。

這個包含關係是 P 對 NP 圖景中堅實而已證明的部分，並為真正的問題鋪好舞台。我們確知 P ⊆ NP。我們不知道的是這個包含是否嚴格，也就是 NP 是否含有 P 所沒有的問題。幾乎所有人都猜它是嚴格的（P 不等於 NP），意思是存在易於驗證卻真正難以求解的問題，但證明已抵抗了數十年的努力。把邏輯理清：P ⊆ NP 是定理；P 不等於 NP 是猜想。