C-SAT和SAT的区别是什么？

Question

这两个NP完全问题到底有什么区别？在我看来，他们都在问一个布尔公式是否可以满足(即输出1)，但一个是在电路的上下文中，而另一个只是公式。然而，人们不能从布尔电路中写出布尔公式吗？

Answer 1

你说得对，他们彼此很接近。任何C-SAT问题都可以表示为SAT，任何SAT问题都可以表示为C-SAT。有一个问题是如何以最有效的方式翻译C-SAT <-> SAT。有些任务更好地表示为SAT，其中一些“看起来”更好地表示为C-SAT。

此外，还有一些SAT求解器在内部使用电路表示法，而不是更流行的子句形式。

此外，您还可以阅读这个很棒的调查：M. Bjork, 2009, Successful SAT encoding techniques