平面SAT

コンピュータサイエンスにおいて、平面 3 満足可能性問題(略称PLANAR 3SATまたはPL3SAT ) は、古典的なブール 3 満足可能性問題を平面 接続グラフに拡張したものです。言い換えれば、変数と節で構成される接続グラフを平面に埋め込むことができるブール式の変数を、式がTRUE と評価されるように一貫して TRUE または FALSE の値に置き換えることができるかどうかを問うものです。この場合、式は満足可能と呼ばれます。一方、そのような割り当てが存在しない場合、式によって表される関数はすべての可能な変数割り当てに対してFALSEとなり、式は満足不可能 になります。たとえば、式「a AND NOT b 」は、( a AND NOT b ) = TRUE となる値a  = TRUE およびb = FALSE を見つけることができるため、満足可能です。対照的に、「a AND NOT a」は満たされません。

3SATと同様に、 PLANAR-SAT はNP 完全であり、リダクションでよく使用されます。

すべての 3SAT 問題は、次の方法で接続グラフに変換できます。すべての変数 に対して、グラフには 1 つの対応するノード があり、すべての節 に対して、グラフには 1 つの対応するノード があります。またはが にある場合は常に、変数と節の間に エッジが作成されます。正のリテラルと負のリテラルは、エッジの色付けを使用して区別されます。 ${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle c_{j}}$${\displaystyle c_{j}.}$${\displaystyle (v_{i},c_{j})}$${\displaystyle v_{i}}$${\displaystyle c_{j}}$${\displaystyle v_{i}}$${\displaystyle \lnot v_{i}}$${\displaystyle c_{j}}$

式が満たされるのは、各変数ノードに TRUE または FALSE を割り当てる方法があり、すべての節ノードが正のエッジによって少なくとも 1 つの TRUE に接続されているか、負のエッジによって FALSE に接続されている場合のみです。

平面グラフとは、2 つの辺が互いに交差しないように平面上に描画できるグラフです。平面 3SAT は、ブール式の変数と節の接続グラフが平面である 3SAT のサブセットです。これは制限された変種でありながら NP 完全であるため重要です。多くの問題 (ゲームやパズルなど) は、非平面グラフを表現できません。したがって、平面 3SAT は、それらの問題が NP 困難であることを証明する方法を提供します。

以下の証明スケッチはD.リヒテンシュタインの証明に従っている。^[1]

自明なことに、 PLANAR 3SAT はNPに属します。したがって、 3SATからの簡約によってNP 困難であることを示すだけで十分です。

この証明では、 が に等しく、 がに等しいという事実を利用しています。 ${\displaystyle (\lnot a\lor \lnot b\lor c)\land (a\lor \lnot c)\land (b\lor \lnot c)}$${\displaystyle (a\land b)\leftrightarrow c}$${\displaystyle (a\lor \lnot b)\land (\lnot a\lor b)}$${\displaystyle a\leftrightarrow b}$

まず、3SAT 式の発生グラフを描きます。2 つの変数または節が接続されていないため、結果として得られるグラフは二部グラフになります。結果として得られるグラフが平面ではないと仮定します。エッジ ( a、c ₁ ) と ( b、c ₂ ) のすべての交差に対して、9 つの新しい変数a ₁、b ₁、α、β、γ、δ、ξ、a ₂、b ₂を導入し、すべてのエッジの交差を図に示す交差ガジェットに置き換えます。これは、次の新しい節で構成されます。

$${\displaystyle {\begin{array}{ll}(\lnot a_{2}\lor \lnot b_{2}\lor \alpha )\land (a_{2}\lor \lnot \alpha )\land (b_{2}\lor \lnot \alpha ),&\quad {\text{i.e.,}}\quad a_{2}\land b_{2}\leftrightarrow \alpha \\(\lnot a_{2}\lor b_{1}\lor \beta )\land (a_{2}\lor \lnot \beta )\land (\lnot b_{1}\lor \lnot \beta ),&\quad {\text{i.e.,}}\quad a_{2}\land \lnot b_{1}\leftrightarrow \beta \\(a_{1}\lor b_{1}\lor \gamma )\land (\lnot a_{1}\lor \lnot \gamma )\land (\lnot b_{1}\lor \lnot \gamma ),&\quad {\text{i.e.,}}\quad \lnot a_{1}\land \lnot b_{1}\leftrightarrow \gamma \\(a_{1}\lor \lnot b_{2}\lor \delta )\land (\lnot a_{1}\lor \lnot \delta )\land (b_{2}\lor \lnot \delta ),&\quad {\text{i.e.,}}\quad \lnot a_{1}\land b_{2}\leftrightarrow \delta \\(\alpha \lor \beta \lor \xi )\land (\gamma \lor \delta \lor \lnot \xi ),&\quad {\text{i.e.,}}\quad \alpha \lor \beta \lor \gamma \lor \delta \\(\lnot \alpha \lor \lnot \beta )\land (\lnot \beta \lor \lnot \gamma )\land (\lnot \gamma \lor \lnot \delta )\land (\lnot \delta \lor \lnot \alpha ),&\\(a_{2}\lor \lnot a)\land (a\lor \lnot a_{2})\land (b_{2}\lor \lnot b)\land (b\lor \lnot b_{2}),&\quad {\text{i.e.,}}\quad a\leftrightarrow a_{2},~b\leftrightarrow b_{2}\\\end{array}}}$$

元のグラフでエッジ ( a、c ₁ ) が反転されている場合、クロスオーバー ガジェットでも ( a ₁、c _{1 ) を反転する必要があります。同様に、元のグラフでエッジ (} b、c ₂ ) が反転されている場合は、 ( b ₁、c ₂ ) を反転する必要があります。

これらの節が充足可能であるのは、および の場合のみであることは簡単に示せます。 ${\displaystyle a\leftrightarrow a_{1}}$${\displaystyle b\leftrightarrow b_{1}}$

このアルゴリズムは、一定量の新しい追加のみを使用して、各交差を平面上の同等物に変換できることを示しています。交差の数は節と変数の数に関して多項式であるため、削減は多項式です。^[2]

• 変数サイクルを持つ平面 3SAT : ここでは、グラフには発生グラフに加えて、すべての変数を通過するサイクルも含まれており、各節はこのサイクルの内側または外側にあります。結果のグラフは依然として平面である必要があります。この問題は NP 完全です。^[1]
  • ただし、すべての節が変数サイクルの内側にある、またはすべての節が変数サイクルの外側にあるように問題がさらに制限されると、動的計画法を使用して多項式時間で問題を解くことができます。
• リテラルを含む平面3SAT :リテラルと節の二部接続グラフも平面である。この問題はNP完全である。^[1]
• 平面直線 3SAT : グラフの頂点は水平線として表される。各変数はx軸上にあり、各節はx軸の上または下に位置する。変数と節の間の接続はすべて垂直線でなければならない。各節は変数との接続を最大 3 つしか持てず、すべて正かすべて負のいずれかである。この問題は NP 完全である。^[3]
  • 平面単調直線型 3SAT : これは平面直線型 3SAT の変形で、x軸より上の節はすべて正で、x 軸より下の節はすべて負です。この問題は NP 完全^[4]であり、3 つの変数を含む各節にx軸上で隣接する2 つの隣接変数がある場合(つまり、隣接変数の間に水平方向に他の変数が出現しない)、NP 完全のままです。^[5]
• 平面1-in-3SAT : これは1-in-3SATの平面版である。NP完全である。^[6]
  • 平面正直線1-in-3SAT：これは平面正直線1-in-3SATである。NP完全である。^[7]
• 平面NAE 3SAT : この問題はNAE 3SATの平面版です。他の変種とは異なり、この問題は多項式時間で解くことができます。証明は平面最大カットへの還元により行われます。^[8]
• 平面回路SAT : これは回路SATの変形であり、SAT式を計算する回路は平面有向非巡回グラフである。これは式の隣接グラフとは異なるグラフである点に注意する。この問題はNP完全である。^[9]

平面SATからの縮約は、論理パズルのNP完全性証明でよく使われる手法です。これらの例としては、Fillomino、^[10]、 Nurikabe、^[11]、 Shakashaka、^[12]、 Tatamibari、^[13]、Tentai Show ^[14]などがあります。これらの証明では、信号（ブール値）を運ぶ配線、入力ゲートと出力ゲート、信号スプリッター、NOTゲート、AND（またはOR）ゲートをシミュレートできるガジェットを構築して、任意のブール回路の平面埋め込みを表します。回路は平面であるため、配線の交差を考慮する必要はありません。

これは、固定された辺の長さと角度を持つ多角形鎖が交差のない平面構成を持つかどうかを判断する問題です。平面単調直線3SATからの還元により、強くNP困難であることが証明されています。 ^[15]

これは、分割に使用されるすべてのエッジの合計長さが可能な限り短くなるように、 ポリゴンをより単純なポリゴンに分割する問題です。

図形が直線多角形で長方形に分割され、多角形に穴がない場合、問題は多項式です。しかし、穴（退化した穴、つまり単一の点）が含まれている場合、平面SATからの帰着により、問題はNP困難です。図形が任意の多角形で凸図形に分割される場合も同様です。^[16]

関連する問題として、最小重量三角形分割（辺の長さの合計が最小の三角形分割を見つける）がある。この問題の決定バージョンは、平面1-in-3SATの変種からの削減によりNP完全であることが証明されている。^[17]