回路の充足可能性問題
コンピュータサイエンスにおける古典的なNP完全問題
左側の回路は充足可能ですが、右側の回路は充足できません

理論計算機科学において、回路の充足可能性問題（ CIRCUIT-SAT、CircuitSAT、CSATなどとも呼ばれる）は、与えられたブール回路に入力を割り当てると出力が真になるかどうかを判断する決定問題である。 [1]言い換えれば、与えられたブール回路への入力を一貫して1または0に設定して回路が1を出力するかどうかが問われる。そうなる場合、回路は充足可能と呼ばれる。そうでない場合、回路は充足不可能と呼ばれる。右の図では、左の回路は両方の入力を1に設定することで充足できるが、右の回路は充足不可能である。

CircuitSATはブール充足可能性問題（SAT）と密接な関連があり、同様にNP完全であることが証明されている。[2]これは典型的なNP完全問題であり、Cook–Levinの定理はSATではなくCircuitSATで証明されることがあり、その場合CircuitSATを他の充足可能性問題に還元してそれらのNP完全性を証明できる。[1] [3]任意のバイナリゲートを含む回路の充足可能性は時間で判定できる。[4] m {\displaystyle m} O （ 2 0.4058 m ) {\displaystyle O(2^{0.4058m})}

NP完全性の証明

回路と満足する入力集合が与えられた場合、各ゲートの出力を定数時間で計算できます。したがって、回路の出力は多項式時間で検証可能です。したがって、回路SATは計算量クラスNPに属します。NP困難性を示すために、 3SATから回路SATへの 縮約を構築することができます

元の3SAT式に変数、演算子（AND、OR、NOT）があるとします。各変数に対応する入力と、各演算子に対応するゲートを持つ回路を設計します。ゲートは3SAT式に従って接続します。例えば、3SAT式が の場合、回路には3つの入力、ANDゲート1つ、ORゲート1つ、NOTゲート1つがあります。 に対応する入力は反転されてANDゲートに送られ、ANDゲートの出力はORゲートに送られます。 × 1 、 × 2 、 … 、 × n {\displaystyle x_{1},x_{2},\dots,x_{n}} y 1 、 y 2 、 … 、 y k {\displaystyle y_{1},y_{2},\dots,y_{k}} （ ¬ × 1 ∧ × 2 ) ∨ × 3 、 {\displaystyle (\lnot x_{1}\land x_{2})\lor x_{3},} × 1 {\displaystyle x_{1}} × 2 、 {\displaystyle x_{2},} × 3 。 {\displaystyle x_{3}.}

3SAT式は上記で設計した回路と等価であることに注目してください。したがって、同じ入力に対して出力は同じです。したがって、3SAT式に条件を満たす割り当てがある場合、対応する回路は1を出力し、その逆も同様です。したがって、これは有効な帰着であり、回路SATはNP困難です。

これにより、回路 SAT が NP 完全であることの証明が完了します。

平面回路SAT

ちょうど2つの入力を持つNANDゲートのみを含む平面ブール回路（つまり、基礎グラフが平面であるブール回路）が与えられていると仮定します。平面回路SATは、この回路の入力の割り当てが出力を真にするかどうかを判断する決定問題です。この問題はNP完全です。さらに、回路内の任意のゲートがNORゲートになるように制約を変更した場合でも、結果として生じる問題はNP完全のままです。[5]

回路不適合

回路不適合は、与えられたブール回路が、その入力のすべての可能な割り当てに対して偽を出力するかどうかを判定する決定問題です。これは回路適合問題の補問題であり、したがって共NP完全です

CircuitSATからの縮約

CircuitSATまたはその派生からの縮約は、特定の問題のNP困難性を示すために使用でき、デュアルレールおよびバイナリロジック縮約の代替手段を提供します。このような縮約に必要なガジェットは次のとおりです

  • ワイヤーガジェット。このガジェットは回路内のワイヤーをシミュレートします。
  • 分割ガジェット。このガジェットは、すべての出力ワイヤが入力ワイヤと同じ値を持つことを保証します。
  • 回路のゲートをシミュレートするガジェット。
  • 真のターミネータガジェット。このガジェットは、回路全体の出力を強制的に真にするために使用されます。
  • 方向転換ガジェット。このガジェットを使えば、必要に応じて配線を正しい方向に向けることができます。
  • クロスオーバーガジェット。このガジェットを使うと、2本のワイヤーを干渉することなく交差させることができます。

マインスイーパ推論問題

この問題は、マインスイーパのボードが与えられたときに、すべての爆弾を見つけることができるかどうかを問うものです。回路UNSAT問題からの縮約により、co-NP完全であることが証明されています。 [6]この縮約のために構築されたガジェットは、ワイヤ、スプリット、ANDゲート、NOTゲート、およびターミネータです。[7]これらのガジェットに関して、3つの重要な観察があります。まず、スプリットガジェットはNOTガジェットおよびターンガジェットとしても使用できます。次に、ANDガジェットとNOTガジェットを構築すれば十分です。なぜなら、これらを組み合わせることで、汎用NANDゲートをシミュレートできるからです。最後に、3つのNANDを交差なしで構成してXORを実装でき、XORはクロスオーバーを構築するのに十分であるため、[8]これにより、必要なクロスオーバーガジェットが得られます

ツェイティン変換

Tseytin変換は、 Circuit-SAT からSATへの直接的な縮約です。回路が 2 入力NAND ゲート(機能的に完全なブール演算子のセット)だけで構成されている場合、変換の記述は簡単です。回路内のすべてのネットに変数を割り当て、各 NAND ゲートに対して、連言正規形節 ( v 1 ∨ v 3 ) ∧ ( v 2 ∨ v 3 ) ∧ (¬ v 1 ∨ ¬ v 2 ∨ ¬ v 3 ) を構築します。ここで、v 1とv 2は NAND ゲートへの入力であり、v 3は出力です。これらの節は、3 つの変数間の関係を完全に記述します。すべてのゲートの節を、回路の出力変数が true になるように制約する追加の節と結合すると、縮約が完了します。全ての制約を満たす変数の割り当ては、元の回路が満足可能であり、任意の解が回路出力を1にする入力を見つけるという元の問題に対する解である場合にのみ存在します。[1] [9]逆、つまりSATが回路SATに還元可能であることは、ブール式を回路として書き直してそれを解くことによって自明になります。

参照

参考文献

  1. ^ abc David Mix BarringtonとAlexis Maciel（2000年7月5日）「講義7：NP完全問題」（PDF）
  2. ^ Luca Trevisan (2001年11月29日). 「講義23：Circuit-SATのNP完全性に関するノート」(PDF) . 2011年12月26日時点のオリジナル(PDF)からアーカイブ。 2012年2月4日閲覧。
  3. ^ また、例えば、スコット・アーロンソンの講義「デモクリトス以降の量子コンピューティング」の講義ノートに記載されている非公式の証明も参照してください。
  4. ^ Sergey Nurk (2009年12月1日). 「Circuit SATのO(2^{0.4058m})の上限」.
  5. ^ 「アルゴリズムの下限値: MIT での困難性証明の楽しみ」(PDF)。
  6. ^ スコット, アラン; ステゲ, ウルリケ; ヴァン・ルーイ, アイリス (2011年12月1日). 「マインスイーパはNP完全ではないかもしれないが、それでも難しい」.数学インテリジェンサー. 33 (4): 5– 17. doi :10.1007/s00283-011-9256-x. ISSN  1866-7414. S2CID  122506352.
  7. ^ Kaye, Richard (2000年3月). 「マインスイーパはNP完全である」(PDF) . The Mathematical Intelligencer . 22 (2): 9– 15. doi :10.1007/BF03025367. S2CID  122435790.
  8. ^ ファイル:Crossover xor.gifとファイル:Crossover nand.pdfを参照
  9. ^ Marques-Silva, João P. and Luís Guerra e Silva (1999). 「バックトラック探索と再帰学習に基づく組み合わせ回路の充足可能性アルゴリズム」(PDF)。2022年7月2日時点のオリジナル(PDF)からのアーカイブ。
「https://en.wikipedia.org/w/index.php?title=Circuit_satisfiability_problem&oldid=1295092618」より取得