algorithm - 第一个被称为 NP Complete 的算法是什么？

Question

应该有一个初始问题来开始构建 NPC 问题集。只有这样，问题才能从集合 NP 添加到集合 NPC 中，表明 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