问第一个被标记为NP完全的算法是什么？
EN

Stack Overflow用户

提问于 2012-12-08 10:11:49

回答 1查看 89关注 0票数 0

在开始构建NPC问题集时，应该有一个初始问题。只有这样，才能通过证明NP中的问题可以简化为NP中的第一个问题，将问题添加到集合NP中。那么，加入全国人大的第一个问题是什么，又是如何得出这个问题确实是全国人大的呢？

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

发布于 2012-12-08 10:41:15

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

历史：

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

证明：

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

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/13773763

复制

相似问题

问第一个被标记为NP完全的算法是什么？EN