1-in-k SATの完全な解決規則

Question

CNF SATでは、各句（AまたはBまたはCまたは...）には少なくとも1つの真のリテラルが含まれていなければなりません。解像度規則は、正確に1つの反対側のリテラルを持つ句のペアに適用されます。

（aまたはbまたはc）と（！aまたはdまたはe）=>（bまたはcまたはdまたはe）

この規則は完全であると言っていますが、式が不満足な場合は、1つの空の句が生成されるまで、（ハードインスタンス、指数回数）ルールを徹底的に適用することで証明できます。式が固有の解を持つ場合、すべてのUNIT句が作成されるまでルールを適用できます。

1-in-k satは、句（A、B、C、...）= 1あたりの正確な1つの変数が正確にあるNP完全なバリアントです。1つの反対のリテラル、そして共通のリテラルを持たない組の句を考えると、私は3番目のものも生産することができます：

（a、b、c）= 1、（！a、d、e）= 1=>（b、c、d、e）= 1

質問：この規則は、不満足で一意に満足できる1-in-k式のための完全ですか？

Answer 1

それが純粋に構文的な規則であるかのように解決を扱います。それは従来のCNF句でそのように機能しますそれは基礎となる推論の規則に対応しているので。ただし、Trueの追加の制限があるCNF句は、TRUEであることを許される1つのリテラルだけが、解像度ルールを正しく適用できるものには対応しません。

ブール式 $（A \ Lor B）\ Land（\ lnot {a} \ lor \ lnnot {b}）\ lors（\ lnot {a} \ lor b）$ は、 1-in-k-sat 式として不満足ですが、解像度ルールを正しく適用すると、 $ a= false、b= true$ （誤った）解決策。