如果一個問題可以找到一個能在多項式的時間裡解決它的演算法，那麼這個問題就屬於P問題。

P是英文單詞多項式的第一個字母。哪些問題是P類問題呢？通常NOI和NOIP不會出不屬於P類問題的題目。我們常見到的一些資訊奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時間的超時程式不會涵蓋任何有價值的演算法。

NP問題不是非P類問題。NP問題是指可以在多項式的時間裡驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間裡猜出一個解的問題。

之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的演算法。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的演算法。相信讀者很快明白，資訊學中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關係。

很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關鍵是，人們想知道，是否所有的NP問題都是P類問題。我們可以再用集合的觀點來說明。如果把所有P類問題歸為一個集合P中，把所有NP問題划進另一個集合NP中，那麼，顯然有P屬於NP。現在，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？通常所謂的“NP問題”，其實就一句話：證明或推翻P=NP。

NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然後，所有的NP問題都可以約化到它。證明一個問題是NPC問題也很簡單。先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它這樣就可以說它是NPC問題了。