私は以前の試験用紙を見ていて、私を混乱させたこの質問に出会った。すべての2-Sat Prequblemが同等の2-SAT pr0blemに変換されない
質問：
同等の2-SAT問題の条項
{x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1}によって与えられていない、すべて等しく2-SAT問題に変換します。 （ヒント：2-SAT問題には10節が含まれています）。
私の理解から、これは単に各節の各リテラルの否定を見つけることですか？したがって、たとえば、{x1, x2} = {-x1, -x2}、これは各節で行われますか？ これが正しいですか？
これは間違いありません。具体的には、すべての句(x ∨ y)を(x ∨ y) ∧ (~x ∨ ~y)に置き換えます。これは文字通り「xまたはyは真でなければならず、xまたはyは偽でなければならない」、またはを満足し、xとyのいずれかが偽であることを確認します。
まず、NAE 2-SAT問題が満足できるものであると仮定します。 Aを満足する代入とし、{x, y}を任意の句とする。 xとyのいずれかが真であることから、これは(x ∨ y) ∧ (~x ∨ ~y)が真であることを意味します。したがって、2-SAT式の対応する2つの節が満たされる。 {x, y}が任意に選ばれたので、Aは2-SAT式のすべての節を満たすと結論付ける。
逆に、NAE 2-SATは満足できるものではないとします。つまり、任意の割り当てに対して、xとyのどちらかがtrueまたは両方ともfalseであるいくつかの句{x, y}が存在します。 Aを任意に選択した代入とし、{x, y}をAが満たさない節（NAE 2-SAT）とする。 x = y以降、これは(x ∨ y) ∧ (~x ∨ ~y)がfalseであることを意味します（接続の半分の1つがfalseなので）。したがって、Aは2-SAT式を満たさない。 Aは任意に選択されたので、2-SAT式を満たす割り当てはないと結論づける。
あなたのソリューションに正しい数の句があることは明らかです。したがって、NAE-2-SATに対する任意の満足のいく解決策が、あなたの構築された2-SATのインスタンスを満たすことを証明するだけです逆に。 –
返事、ありがとうございました。NAE2ATの問題を解決できない場合はどうすればよいですか？ – user6227505
実際にあなたが「満足」するケースの両方向を実証しているなら、その可能性について心配する必要はありません:)なぜ、NAE-2-SAT問題に対する解決策がないと考えてください。あなたが構築した2-SATインスタンスに対する*満足する解決策がNAE-2-SAT問題に対する満足のいく解決策になることが証明されているので、2-SATインスタンスに対する満足のいく解決策もないことが必要です。 - もし存在するならば、その解決法はNAE-2-SATのインスタンスも満たすだろう。それは解決策がないという仮定に反する。 –