NPの2SAT方程式のシステムを発見しています。

Question

またはGate（以下のDNF形式）によって存在した特定の数の2SAT方程式に対する解決策を発見するかどうかを知りたいのですが（以下のDNF形式）。

式は合計N個の変数を有し、各句は1からnの変数のサブセット内の2SAT方程式である。 例：

f= [（x1 || x 2）&&（！x 2 || x 3）&&（x 3 || x 4）] ||[（x2 || x5）&&（x3 || x6）&&（！x4 ||！x6）]....

式fは、M句を有する2SAT方程式のDNFである。NPでこれへの解決策を見つけていますか？もしそうなら、どのように？

また、式fの偽のインスタンスを見つけるかどうかについても知りたいです。

Answer 1

• 最初に、 $ p $ は $のサブセットです。 np $ 。 Yuval映画様のコメントも参照してください。 $ p $ 、または $ np \のがが意図したものを仮定します。 setminus p $ 。
• また、「DNF」という名前は、具体的には、 Elementary 結合の分離を指し、任意の機能の分類は不潔ではありません。説明しているものはDNFではなく、CNFの異議肢です。

それなりのものでは、ここに私の答えがあります。

---

1. 2-CNFの分離を満たすために、必要なのは、 one を満たすことだけです。したがって、2 SATアルゴリズムを最初のCNFSに適用して「はい」になると、問題全体への答えは「はい」です。それ以外の場合は、2番目のものに移動するだけです。あなたがそれらの m を持っているので、時間はかかりません。それらのどれも個別に満たすことができるならば、すなわちそれらはすべて一定のゼロであるので、明らかに全体が一定のゼロである。

   だから最初の部分への答えは次のとおりです。問題はPにあり、次の決定アルゴリズムがあります：

   2-CNFごとに、「通常の」2-SATアルゴリズム（解像度ルール）を適用して、満足できるかどうかを判断します。 「はい」の場合は、「はい」を返します。 「はい」を見つけることなくすべてを通過した場合は、「いいえ」を返します。

---

2. 今、その式の「偽」ケース（TAUTOLYの問題とも呼ばれる）を見つけることは完全に別の質問です。一つのことにとって、またはORSの飼料のためのTAUTOLYは、De Morganの規則によるおよびそれからORSの充足性と同等です。しかし、それはすでに一般的なSAT問題のより一般的なケースです、それはそうではありませんか？

   可能な式のセットを2要素の切り離しに制限するときに何が起こるかを検討してください。繰り返します。だからそれは同じようなものです $$ f= [（x_1 \ vee x_1）\＆（\ neg x_2 \ vee \ neg x_2）\＆（x_3 \ vee x_3）] \ vee [（x_2 \ vee x_2）\＆（x_4 \ vee x_4）\＆（ X_5 \ VEE X_5）] \ vee ... $$ これはに相当します $$ F= [X_1 \＆\ NEG X_2 \ 2 \ 3] \ VEY [X_2 \＆X_4 \＆X_5] \ vee ... $$ これは通常のDNFです。 DE MORGAN Transformationの後、あなたは通常のCNFを得、その満足性はNP-HARDであることがわかっています。したがって、この1つのをサブセットとして含む問題は、少なくともNP硬質である。

   明らかに、問題の問題は NPの外側にあるという問題は、まだ多項式的に検証可能ではありません。だからあなたの2番目の質問への答えは「NPではなく、pではなく」です。