平面1-in-3 SATの平面条件

Question

平面3SAT NPが完全です。平面3SATインスタンスは、次のルールを使用して構築されたグラフが平面である3SATインスタンスです。

1. $ x_i $ and $ bar {x_i} $ごとに頂点を追加します
2. すべての節$ c_j $に頂点を追加します
3. $（x_i、 bar {x_i}）$ペアごとにエッジを追加します
4. Vertex $ x_i $（または$ bar {x_i} $）のエッジを各頂点に追加する節を表す節を表します
5. 2つの連続した変数$（x_1、x_2）、（x_2、x_3）、...、（x_n、x_1）$の間にエッジを追加します

特に、ルール5は、2つの異なる領域で条項を分割する「バックボーン」を構築します。

平面1-in-3 SAT NPが完全です。

しかし、平面1-in-3 SATの場合、平面3SATと同じように平面性条件は定義されていますか？特に、変数$（x_i、x_ {i+1}）$をリンクするバックボーンがあると仮定できますか？

Answer 1

はい、できます。実際、あなたはより強いものが真実であることを示すことさえできます。問題はASを知っています 正の平面1-in-3-sat 示されているようにNPが完全です ムルツァーとルート.

1-in-3-SATのこのバージョンでは、すべての入力式に

• 句ごとに3つの変数がありますが、どれも否定されていません
• 変数の頂点に「バックボーン」を追加しても、式のグラフは平面です

削減はからです 平面3-SAT.