C-SATとSATの違いは？

Question

これらの2つのNP完全問題の違いは何ですか？ブール式を満たすことができるか（すなわち出力1）、一方は回路の文脈にあり、もう一方は単なる式であるかどうかを問われているように思える。しかし、ブール式回路からブール式を書くことはできませんでしたか？

Answer 1

あなたは正しいです、彼らはお互いに非常に近いです。どのC-SAT問題もSATとして表すことができ、どのSAT問題もC-SATとして表すことができます。最も効率的な方法でC-SAT < - > SATをどのように翻訳するのかという疑問があります。いくつかのタスクはSATとして表現する方が良いですが、その中にはC-SATよりも優れているものもあります。

さらに、一般的なクロスタル形式ではなく、内部的に回路表現を使用するSATソルバーがあります。

さらに、この素​​晴らしいアンケートを読むことができます：M. Bjork, 2009, Successful SAT encoding techniques