一個決定性問題 C若是為NPC，則代表它對NP是完備的，這表示：
它是一個NP問題，且
其他屬於NP的問題都可歸約成它。
1.它是一個NP問題，且
2.其他屬於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年出版的書之中。
滿足條件2（無論是否滿足條件1）的問題集合被稱為NP-hard。一個NP-hard問題至少跟NPC問題一樣難。 有一類問題已經被證明屬於NP-hard但不屬於NP，即，這類問題至少與NP-complete一樣難，但這類問題又不屬於NP（自然也不屬於NP-complete）。 例如圍棋的必勝下法，就是這樣一個問題。
