平面SAT – 日本語百科事典辞書

Planar_SAT

コンピューターサイエンスにおける平面3 充足可能性問題( PLANAR 3SATまたはPL3SATと略称) は、古典的なブール 3 充足可能性問題を平面入射グラフに拡張したものです。言い換えれば、指定されたブール式 (変数と節で構成される出現グラフを平面に埋め込むことができる) の変数を、式が TRUEと評価されるように一貫して TRUE または FALSE の値で置き換えられるかどうかを尋ねます。。この場合、この式は充足可能と呼ばれます。。一方、そのような割り当てが存在しない場合、式で表される関数はすべての可能な変数割り当てに対してFALSEとなり、式は満たされません。たとえば、式「a AND NOT b 」は、値a = TRUE およびb = FALSEが見つかり、( a AND NOT b ) = TRUE となるため、満たされます。対照的に、「a AND NOT a」は満たされません。
平面 SAT 問題の例。黒いエッジは非反転変数に対応し、赤いエッジは反転変数に対応します。
3SATと同様、PLANAR-SAT はNP 完全であり、リダクションでよく使用されます。
コンテンツ
1 意味
2 NP完全性の証明
3 亜種と関連する問題
4 削減
4.1 ロジックパズル 4.2 固定角度チェーンの平坦折り 4.3 最小エッジ長パーティション
5 参考文献

意味
すべての 3SAT 問題は、次の方法で発生率グラフに変換できます。すべての変数についてv I
{ v_{i}}
$v_{i}""$
、グラフには対応するノードが 1 つありますv I
{ v_{i}}

、そしてすべての節についてc j
{ c_{j}}

、グラフには対応するノードが 1 つあります c j { c_{j}.}
縁 ( vI c j)
{ (v_{i}，c_{j})}

変数の間に作成されますv I
{ v_{i}}

と句c j
{ c_{j}}

いつでもv I
{ v_{i}}

また￣ v I
{ lnot v_{i}}

いるc j
{ c_{j}}

。正のリテラルと負のリテラルは、エッジの色付けを使用して区別されます。
この式は、すべての節ノードが正のエッジによって少なくとも 1 つの TRUE に接続されるか、負のエッジによって FALSE に接続されるように、各変数ノードに TRUE または FALSE を割り当てる方法がある場合にのみ満たされます。
平面グラフは、2 つのエッジが互いに交差しないように平面上に描画できるグラフです。平面 3SAT は、ブール式の変数と節の出現グラフが平面である3SAT のサブセットです。これは制限されたバリアントであり、依然として NP 完全であるため、これは重要です。多くの問題 (ゲームやパズルなど) では、非平面グラフを表現できません。したがって、Planar 3SAT は、これらの問題が NP 困難であることを証明する方法を提供します。

NP完全性の証明

左側が交差点です。右側がクロスオーバーガジェットです。小さな点は文節を表します。黒と赤のエッジは、それぞれ非反転変数と反転変数に対応します。
次の証明スケッチは、D. リキテンシュタインの証明に従っています。
自明のことですが、PLANAR 3SAT はNPにしたがって、 3SATからの還元によってNP 困難であることを示すだけで十分です。
この証明は次の事実を利用しています。( ￣
ある∨ ￣ b ∨ c ) ∧( ある∨ ￣ c ) ∧( b∨ ￣ c )
{ (lnot alor lnot blor c)land (alor lnot c)land (blor lnot c)}

と同等です( ある∧ b ) ⇔ c
{ (aland b)Leftrightarrow c}

そしてそれ( ある∨ ￣ b ) ∧( ￣
ある∨ b )
{ (alor lnot b)land (lnot alor b)}

と同等です
ある⇔ b
{ aLeftrightarrow b}
まず、3SAT式の発生率グラフを描きます。2 つの変数または節が接続されていないため、結果のグラフは2 部になります。結果のグラフが平面的ではないとします。エッジ ( a ， c 1 ) と ( b ， c 2 )の交差ごとに、9 つの新しい変数a 1、b 1、α、β、γ、δ、ξ、a 2、b 2を導入し、次のすべての交差を置き換えます。図に示すクロスオーバーガジェットを使用したエッジ。これは次の新しい条項で構成されます。 ( ￣ある2
￣ 2 α ) ∧(ある2 ￣ α ) ∨(b2 ￣ α
) つまり、
ある2 2 α ( ￣
ある2 1 β ) ∧(ある2 ￣ β ) ∨( ￣ 1 ￣ β
) つまり、
ある2
￣ 1 β (ある1 1 γ ) ∧( ￣
ある1 ￣ γ ) ∨( ￣ 1 ￣ γ
) つまり、￣ある1
￣ 1 γ (ある1
￣ 2 δ ) ∧( ￣
ある1 ￣ δ ) ∨(b2 ￣ δ
) つまり、￣ある1 2 δ ( α∨ β ∨ ξ ) ∧( γ∨ δ ∨ ￣ ξ
) つまり、α ∨ β ∨ γ ∨ δ( ￣α ∨ ￣ β ) ∧( ￣β ∨ ￣ γ ) ∧( ￣γ ∨ ￣ δ ) ∧( ￣δ ∨ ￣ α
) (ある2 ￣ある) ∧( ある∨ ￣る 2) ∧(b2 ￣ b ) ∧( b∨ ￣ b 2) つまり、
ある⇔ る 2 b
⇔ 2
{ {begin{array}{ll}(lnot a_{2}lor lnot b_{2}lor alpha )land (a_{2}lor lnot alpha )lor (b_ {2}lor lnot alpha )，&quad {text{ie，}}quad a_{2}land b_{2}Leftrightarrow alpha \(lnot a_{2}lor b_ {1}lor beta )land (a_{2}lor lnot beta )lor (lnot b_{1}lor lnot beta )，&quad {text{ie，}} quad a_{2}land lnot b_{1}Leftrightarrow beta \(a_{1}lor b_{1}lor gamma )land (lnot a_{1}lor lnot gamma )lor (lnot b_{1}lor lnot gamma )，&quad {text{ie，}}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 )lor (b_{2}lor lnot delta ) ，&quad {text{ie，}}quad lnot a_{1}land b_{2}Leftrightarrow delta \(alpha lor beta lor xi )land (gamma lor delta lor lnot xi )，&quad {text{ie，}}quad alpha lor beta lor gamma lor delta \(lnot alpha lor lnot ベータ )land (lnot beta lor lnot gamma )land (lnot gamma lor lnot delta )land (lnot delta lor lnot alpha )，&\(a_ {2}lor lnot a)land (alor lnot a_{2})land (b_{2}lor lnot b)land (blor lnot b_{2})，& quad {text{ie，}}quad aLeftrightarrow a_{2}，~bLeftrightarrow b_{2}\end{配列}}}

元のグラフでエッジ ( a ， c 1 ) が反転されている場合、クロスオーバーガジェットでも( a 1 ， c 1 ) が反転される必要が同様に、エッジ ( b ， c 2 ) がオリジナルで反転されている場合は、( b 1 ， c 2 ) も反転する必要が
これらの条項が満たされるのは、次の場合に限ります。
ある ⇔ ある 1 { aLeftrightarrow a_{1}}
と b ⇔ b 1
{ bLeftrightarrow b_{1}}
${ bLeftrightarrow b_{1}}$ このアルゴリズムは、一定量の新しい追加のみを使用して、各交差点を平面上の等価物に変換できることを示しています。交差の数は節と変数の数に関して多項式であるため、リダクションも多項式になります。

亜種と関連する問題
変数サイクルを使用した平面 3SAT : ここでは、発生率グラフに加えて、グラフにはすべての変数を通過するサイクルも含まれており、各節はこのサイクルの内側または外側に結果として得られるグラフは依然として平面である必要がこの問題は NP 完全です。
ただし、すべての節が変数サイクルの内側にある、またはすべての節が変数サイクルの外側にあるなど、問題がさらに制限されている場合は、動的計画法を使用して問題を多項式時間で解くことができます。
リテラルを含む平面 3SAT :リテラルと句の 2 部発生グラフも平面です。この問題は NP 完全です。
平面直線 3SAT : グラフの頂点は水平線分として表されます。各変数はx軸上にあり、各節はx軸の上/下に変数と文節の間のすべての接続は垂直セグメントである必要が各節には変数との接続が 3 つまでしかなく、すべて肯定かすべて否定のいずれかになります。この問題は NP 完全です。
平面モノトーン直線 3SAT : これは平面直線 3SAT の変形であり、 x軸より上の節はすべて正であり、x 軸より下の節はすべて負です。この問題は NP 完全であり、3 つの変数を含む各節にx軸上で隣接する 2 つの隣接変数がある(つまり、隣接する変数の間に水平方向に他の変数が現れない) 場合は NP 完全のままです。
Planar 1-in-3SAT : これは1-in-3SATと同等の平面です。NP完全です。
平面ポジティブ直線 1-in-3SAT : これは、ポジティブ1-in-3SATと同等の平面です。NP完全です。
平面 NAE 3SAT : この問題はNAE 3SATと同等の平面です。他の変形とは異なり、この問題は多項式時間で解決できます。証明は、平面最大カットへの縮小によって行われます。
平面回路 SAT : これは回路 SATの変形であり、SAT 式を計算する回路は平面有向非巡回グラフです。これは数式の隣接グラフとは異なるグラフであることに注意してこの問題は NP 完全です。

削減

ロジックパズル
Planar SAT からの還元は、論理パズルの NP 完全性証明で一般的に使用される方法です。これらの例には、フィロミノ、ぬりかべ、シャカシャカ、タタミバリ、、テンタイショーなどがこれらの証明には、任意のブール回路の平面埋め込みを表現するために、信号 (ブール値)、入力および出力ゲート、信号スプリッター、NOT ゲート、および AND (または OR) ゲートを運ぶワイヤーをシミュレートできるガジェットの構築が含まれます。回路は平面的であるため、配線の交差を考慮する必要はありません。

固定角度チェーンの平坦折り
辺の長さと角度が固定された多角形の鎖が交差のない平面形状であるかどうかを判断する問題です。平面単調直線 3SAT からの還元により、NP 耐性が強いことが証明されています。

最小エッジ長パーティション
これは、パーティションで使用されるすべてのエッジの合計の長さができるだけ小さくなるように、ポリゴンをより単純なポリゴンに分割する問題です。
Figure が直線多角形で、それを長方形に分割する必要があり、多角形に穴がない場合、問題は多項式です。しかし、穴が含まれている場合 (縮退した穴 (単一点) であっても) は、平面 SAT からの換算により、問題は NP 困難になります。図形が多角形の場合も同様で、凸図形に分割する必要が
関連する問題は、最小重み三角形分割、つまり最小合計エッジ長の三角形分割を見つけることです。この問題の決定バージョンは、Planar 1-in-3SAT の変形からの削減によって NP 完全であることが証明されています。

参考文献
^ リキテンスタイン、デヴィッド (1982-05-01)。「平面公式とその用途」。SIAM ジャーナルオンコンピューティング。11 (2): 329–343。土井：10.1137/0211025。ISSN 0097-5397。
^ エリック・ディメイン（2015). 「7. 平面SAT」。MIT オープンコースウェア。 CS1 メイン: URL-ステータス (リンク) ^ ラグナサン、アルヴィンド; クヌース、ドナルド E. (1992)。「相性の良い代表者問題」。SIAM J. 離散数学。5 (3): 422–427。arXiv : cs/9301116。Bibcode : 1993cs….1116K。土居：10.1137/0405033。S2CID 9974756。 ^ デ・バーグ、マーク; ホスラヴィ、アミラリ（2010)。「平面内の最適なバイナリ空間パーティション」。コンピューティングと組み合わせ論。コンピューターサイエンスの講義ノート。Vol. 6196。216 ～ 225 ページ。土井: 10.1007/978-3-642-14031-0_25。ISBN 978-3-642-14030-3。
^ アガルワル、パンカジ K.; アロノフ、ボリス。ゲフト、ツヴィカ。ハルペリン、ダン。「接続制約のある両手平面アセンブリのパーティショニングについて」。2021 年離散アルゴリズムに関する ACM-SIAM シンポジウム (SODA) の議事録: 1740–1756。arXiv : 2009.12369。土井: 10.1137/1.9781611976465.105。
^ ダイアー、メイン州; 午前、フリーズ（1986 年 6 月）。「Planar 3DM は NP 完全です」。アルゴリズムのジャーナル。7 (2): 174–184。土井：10.1016/0196-6774(86)90002-7。
^ ヴォルフガング、ミュルツァー; ローテ、ギュンター（2008-05-15)。「最小重み三角形分割は NP 困難です」。ACM のジャーナル。55 (2): 11:1–11:29。arXiv : cs/0601002。土井: 10.1145/1346330.1346336。ISSN 0004-5411。S2CID 1658062。 ^ モレ、BME (1988 年 6月）。「平面 NAE3SAT は P にあります」。SIGACT ニュース。19 (2): 51–54。土井: 10.1145/49097.49099。ISSN 0163-5700。S2CID 17219595。 ^ デメイン、エリック（2015). 「6.サーキットSAT」。ユーチューブ。 CS1 メイン: URL-ステータス (リンク) ^ 谷戸、隆樹（2003). 別の解決策を見つける複雑さと完全性、およびパズルへのその応用。CiteSeerX 10.1.1.103.8380。 ^ マルクス、ホルツァー; クライン、アンドレアス。クトリブ、マーティン（2004)。「ぬりかべペンシルパズルのNP完全性とそのバリエーションについて」(PDF)。第 3 回アルゴリズムを楽しむ国際会議の議事録。S2CID 16082806。2020 年 2 月 11 日のオリジナル(PDF)からアーカイブされました。
外部リンク|journal=(ヘルプ) ^ デメイン、エリック D.; 岡本良雄上原龍平；宇野有志（2014)、「計算量とシャカシャカの整数計画モデル」(PDF)、電子情報通信学会論文誌「エレクトロニクス、通信、計算機科学の基礎」、E97-A (6): 1213–1219、Bibcode : 2014IEITF.. 97.1213D、ドイ：10.1587/transfun.E97.A.1213、hdl：10119/12147
^ アドラー、アビブ; ボスブーム、ジェフリー。デメイン、エリック D. ディメイン、マーティン・L. Liu、Quanquan C.; リンチ、ジェイソン（2020年5月7日）。「畳み張りはNP完備」。arXiv : 2003.08331 。
^ フェルタン、ギョーム; ジャムシディ、シャハラド。コムシエヴィチ、クリスチャン。「渦巻銀河のアルゴリズムガイドに向けて」。理論的なコンピューターサイエンス。586 : 26-39。土井：10.1016/j.tcs.2015.01.051。S2CID 766372 。2021 年8 月 18 日に取得。 ^ デメイン、エリック D.; アイゼンシュタット、サラ（2011)。デーネ、フランク。ジョン・イアコノ。サック、ヨルク＝リュディガー（編）。「固定角チェーンの平坦化はNP耐性が強い」。アルゴリズムとデータ構造。コンピューターサイエンスの講義ノート。シュプリンガーベルリンハイデルベルク。6844 : 314–325。土井: 10.1007/978-3-642-22300-6_27。ISBN 9783642223006。
^ リンガス、アンジェイ; ピンター、ロン Y. ロナルド・L・リベスト、シャミール、アディ (1982)。「直線多角形の最小エッジ長分割」(PDF)。手順第20回アラートン会議共通。コントロールコンピューティング: 53 ～ 63。
^ ヴォルフガング、ミュルツァー; ローテ、ギュンター。「最小重みの三角形分割は NP 困難です」。Ｊ．ＡＣＭ．55 (2): 11:1–11:29。arXiv : cs/0601002。土井: 10.1145/1346330.1346336。ISSN 0004-5411。S2CID 1658062。 “