什麼是第一個被稱爲NP Complete的算法？

Question

應該有一個最初的問題開始建立一套NPC問題。只有這樣才能將問題添加到集合NPC中，從集合NP中顯示出NP中的問題可以簡化爲NPC中的第一個問題。那麼，什麼是第一個被添加到NPC的問題，以及某個人是如何得出結論的，那就是確實是NPC。

（注：谷歌搜索，沒有回答，我希望這裏有人的教授曾提到在課堂上是這樣的。）

Answer 1

這是一個可滿足或SAT問題。

歷史：
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

證明：
http://www.proofwiki.org/wiki/CNF_SAT_is_NP-complete