一個決定性問題C若是為NPC，則代表它對NP是完備的，這表示：
- 它是一個NP問題，且
- 其他屬於NP的問題都可歸約成它。
可歸約在此意指對每個問題L，總有一個多項式時間多對一變換，即一個決定性的算法可以將實例l∈L轉化成實例c∈C，並讓c回答Yes若且唯若此答案對l也是Yes。為了證明某個NP問題A實際上是NPC問題，證明者必須找出一個已知的NPC問題可以變換成A。
本定義得到一個結論，就是若上述的C有一個多項式時間可解的算法，則我們可以將所有的NP問題降到P之中。
這個定義是史提芬·古克所提出。雖然NPC這個詞並沒有出現在這篇論文上任何地方。在這個資訊科學會議上，資訊科學家激動地討論NPC問題是否可以在一個確定型圖靈機上以多項式時間求解。John Hopcroft總結與會眾人的共識，認為由於沒有人能對某一命題提出駁倒對方的證明，此問題不會於現在解決。此命題就是知名的
- P和NP相等嗎?。
尚未有人能提出證明，說明NPC問題是否能在多項式時間中解決，使得此問題成為著名的數學中未解決的問題。 位於劍橋市的“克雷數學研究所”（Clay Mathematics Institute，簡稱CMI）提供了一百萬美金獎金給任何可以證明P=NP或P≠NP的人。
一開始很難相信NPC問題是實際存在的，但著名的古克-李芬定理說明了一切（由Leonid Levin與Cook獨立證出SAT問題是NPC問題，簡化過但依舊艱深的證明在此）。
在1972年，Richard Karp證明有好幾個問題也是NPC（請見卡普的二十一個NP-完全問題），因此除了SAT問題外，的確存在著一整類NPC問題。從古克開始，數千個問題藉由從其他NPC問題變換而證實也是NPC問題，其中很多問題被蒐集在Garey與Johnson於1979年出版的書之中。
