0

应该有一个初始问题来开始构建 NPC 问题集。只有这样,问题才能从集合 NP 添加到集合 NPC 中,表明 NP 中的问题可简化为 NPC 中的第一个问题。那么,第一个添加到NPC的问题是什么,以及如何有人断定它确实是NPC。

(注意:谷歌搜索,没有答案。我希望这里有人的教授在课堂上提到过这样的事情)

4

1 回答 1

2

这是一个可满足性或 SAT 问题。

历史:
http ://en.wikipedia.org/wiki/Boolean_satisfiability_problem

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

于 2012-12-08T02:41:14.627 回答