Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
应该有一个初始问题来开始构建 NPC 问题集。只有这样,问题才能从集合 NP 添加到集合 NPC 中,表明 NP 中的问题可简化为 NPC 中的第一个问题。那么,第一个添加到NPC的问题是什么,以及如何有人断定它确实是NPC。
(注意:谷歌搜索,没有答案。我希望这里有人的教授在课堂上提到过这样的事情)
这是一个可满足性或 SAT 问题。
历史: http ://en.wikipedia.org/wiki/Boolean_satisfiability_problem
证明: http: //www.proofwiki.org/wiki/CNF_SAT_is_NP-complete