<分区>
应该有一个初始问题来开始构建 NPC 问题集。只有这样才能将问题添加到集合 NPC 中,从集合 NP 表明 NP 中的问题可简化为 NPC 中的第一个问题。那么,第一个加入NPC的问题是什么,怎么就有人断定确实是NPC呢。
(注:谷歌搜索,没有答案。我希望这里有人的教授在类里面提到过这样的事情)
<分区>
应该有一个初始问题来开始构建 NPC 问题集。只有这样才能将问题添加到集合 NPC 中,从集合 NP 表明 NP 中的问题可简化为 NPC 中的第一个问题。那么,第一个加入NPC的问题是什么,怎么就有人断定确实是NPC呢。
(注:谷歌搜索,没有答案。我希望这里有人的教授在类里面提到过这样的事情)
最佳答案
这是一个可满足性或 SAT 问题。
历史:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
关于algorithm - 第一个被标记为 NP Complete 的算法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13773763/