这两个 NP 完全问题之间到底有什么区别？在我看来，他们都在询问是否可以满足布尔公式（即输出 1），但一个是在电路的上下文中，另一个只是一个公式。但是，不能从布尔电路中写出一个布尔公式吗？
问问题
466 次
1 回答
2
你是对的，他们彼此非常接近。任何 C-SAT 问题都可以表示为 SAT，任何 SAT 问题都可以表示为 C-SAT。有一个问题如何以最有效的方式翻译 C-SAT <-> SAT。有些任务更好地表示为 SAT，其中一些“看起来”更好地表示为 C-SAT。
此外，还有一些 SAT 求解器在内部使用电路表示，而不是更流行的分句形式。
此外，您可以阅读这份出色的调查：M. Bjork，2009，成功的 SAT 编码技术
于 2017-05-22T01:23:33.627 回答