ガジェット（コンピュータサイエンス）
計算問題のサブユニット

計算複雑性理論において、ガジェットとは、ある計算問題の基本単位の一つの挙動をシミュレートする、問題インスタンスのサブユニットである。ガジェットは通常、NP完全性やその他の計算困難性の証明の一環として、ある計算問題から別の計算問題への縮約を構築するために用いられる。コンポーネント設計技法は、ガジェットを用いて縮約を構築する手法である。[1]

Szabó (2​​009) は、ガジェットの使用を1954年のグラフ理論論文WTutteに遡らせている。この論文で、Tutteは与えられた次数制約を持つ部分グラフを見つける問題を完全マッチング問題に縮減するガジェットを提示した。しかし、「ガジェット」という用語はもっと後の時代に由来し、Tutteの論文には登場しない。[2] [3]

例

3-充足可能性からグラフ3-彩色へのNP完全性縮約。変数と節のガジェットはそれぞれ左上と左下に表示されます。右側は、3つの変数と2つの節を持つ3-CNF式( x ∨ y ∨ ~ z ) ∧ (~ x ∨ ~ y ∨ z )の縮約全体の例です。

多くのNP完全性証明は、3-充足可能性からの多対一還元に基づいています。3-充足可能性とは、ブール式への満足な割り当てを見つける問題です。ブール式は、各節が3つの項の選言（ブールOR）であり、各項がブール変数またはその否定です。この問題から、ハミルトン閉路問題やグラフ彩色などの無向グラフ上の難しい問題への還元は、通常、与えられた3-充足可能性インスタンスの変数と節の挙動をシミュレートするサブグラフ形式のガジェットに基づいています。これらのガジェットは、次に接着されて単一のグラフ、つまり検討中のグラフ問題の難しいインスタンスを形成します。[4]

例えば、グラフの3色可能性をテストする問題は、このタイプの3充足可能性からの縮約によってNP完全であることが証明される可能性があります。この縮約では、「Ground」と「False」というラベルが付いた、どのガジェットにも属さない2つの特別なグラフ頂点が使用されます。図に示すように、変数xのガジェットは、基底頂点と三角形状に接続された2つの頂点で構成されています。ガジェットの2つの頂点のうち1つにはxのラベルが、もう1つにはxの否定のラベルが付けられています。節( t 0 ∨ t 1 ∨ t 2 )のガジェットは、6つの頂点で構成され、図示されている辺によって、互いに、項t 0、t 1、t 2を表す頂点、そして基底頂点とFalse頂点に接続されています。3-CNF式は、変数と節ごとに別々のガジェットを作成し、図のように接続することでグラフに変換できます。[5]

結果のグラフの 3 色分けでは、その 3 色を true、false、ground として指定できます。false と ground は、false 頂点と ground 頂点に割り当てられた色 (これらの頂点は構築によって隣接するため、必然的に異なる) であり、true はこれらの頂点のどちらにも使用されない残りの色です。変数ガジェット内では、2 種類の色分けのみが可能です。変数のラベルが付けられた頂点は、true または false のいずれかの色に塗られなければならず、変数の否定のラベルが付けられた頂点は、それに応じて false または true のいずれかの色に塗られなければなりません。このように、変数ガジェットへの有効な色の割り当ては、変数への真理値の割り当てと 1 対 1 で対応します。つまり、色分けに関するガジェットの動作は、真理値の割り当てに関する変数の動作をシミュレートします。各節の割り当ては、隣接する項頂点の少なくとも1つが真に色付けされている場合、有効な3色化を持ちます。また、隣接する項頂点がすべて偽に色付けされている場合、3色化することはできません。このように、節ガジェットは、対応する真値割り当てが節を満たす場合にのみ色付けできるため、ガジェットの動作は節の動作をシミュレートします。

制限付き削減

アグラワルら（1997）は、ガジェットの一部を記述する各ビットが入力の限られたビット数にのみ依存するという「ガジェット縮小の根本的に単純な形式」と彼らが呼ぶものを検討し、この縮小を使用して、すべてのNP完全集合は多項式時間同型であるというバーマン・ハートマニス予想の類似物を証明した。[6]

NP完全性の標準的な定義には、多項式時間での 多対一縮約が含まれます。NPにおける問題は、NPにおける他のすべての問題に同じタイプの縮約が存在する場合、定義上NP完全です。そして、NPにおける問題がNP完全であることを証明する標準的な方法は、既知のNP完全問題からその問題への多項式時間での多対一縮約を見つけることです。しかし（Agrawalらが「奇妙でよく見られる事実」と呼んだように）、当時NP完全であると知られていたすべての集合は、より強い概念であるAC 0多対一縮約、つまり多項式サイズ、定数の深さ、無制限のファンインを持つ回路で計算できる縮約を用いて完全であると証明できました。Agrawalらは、AC 0縮約においてNP完全であるすべての集合は、多項式サイズ、定数の深さ、無制限のファンインを持つ回路を用いて、さらに制限されたタイプの縮約であるNC 0多対一縮約においても完全であることを証明しました。 NC 0縮約では、縮約の各出力ビットは一定数の入力ビットにのみ依存する。[6]

バーマン＝ハートマニス予想は、計算複雑性理論における未解決問題であり、すべてのNP完全問題クラスは多項式時間同型であるというものである。つまり、AとBが2つのNP完全問題クラスである場合、 AからBへの多項式時間1対1還元が存在し、その逆も多項式時間で計算可能である。Agrawalらは、AC 0還元とNC 0還元の同値性を用いて、AC 0還元の下でNPにとって完全となるすべての集合がAC 0同型であることを示した。[6]

ガジェットの最適化

ガジェットの応用例の一つは、近似困難であることが知られている問題を、その困難さが証明されるべき別の問題に縮約することによって、近似結果の困難性を証明することです。この応用例においては、通常、最初の問題のインスタンス群において目的関数の値にギャップがあり、与えられたインスタンスの目的関数がギャップの低い側にあるか高い側にあるかを判断することが困難です。これらの証明で使用される縮約、および縮約に使用されるガジェットは、このギャップの存在を維持する必要があり、縮約から得られる近似不可能性の強さは、ギャップがどの程度維持されるかに依存します。

Trevisan ら (2000) は、満たされる制約の数を最大化することを目的とする制約充足問題のファミリーについて、ギャップを維持するガジェットを見つける問題を形式化しました。 [7]彼らは、Garey、Johnson、Stockmeyer (1976) による3 充足可能性から2 充足可能性への縮減を例として示しています。この縮減では、3-SAT 節を表すガジェットは 10 個の 2-SAT 節で構成され、3-SAT 節を満たす真理値割り当てはガジェットの少なくとも 7 個の節も満たしますが、3-SAT 節を満たさない真理値割り当てはガジェットの 6 個を超える節も満たしません。[8]このガジェットと、（P = NPでない限り）真理値割り当てが満たす3-SAT節の数を最大化する多項式時間近似スキームが存在しないという事実を使用することで、同様にMAX 2-SATの近似スキームが存在しないことが示されます。

Trevisan らは、彼らが研究する制約充足問題の多くの場合において、最も強い近似不可能性の結果をもたらすガジェットを、線形計画問題の解として自動的に構築できることを示しています。同じガジェットベースの縮約は、逆方向にも使用でき、近似アルゴリズムをより簡単な問題からより難しい問題に移すことができます。たとえば、Trevisan らは、Garey、Johnson、Stockmeyer (1976) のものよりも強力な、3-SAT を重み付き 2-SAT の変種 (重み付き 2-SAT 節 7 つで構成) に縮約する最適なガジェットを提供しています。このガジェットを、MAX 2-SAT 用の既知の半正定値計画法近似アルゴリズムとともに使用することで、従来のアルゴリズムよりも優れた、近似比 0.801 の MAX 3-SAT の近似アルゴリズムを提供しています。

参考文献

  1. ^ Garey, MR ; Johnson, DS (1979)、「3.2.3 コンポーネント設計」、Computers and Intractability: A Guide to the Theory of NP-Completeness、サンフランシスコ、カリフォルニア州: WH Freeman、pp. 72–74、ISBN 0-7167-1045-5、MR  0519066。
  2. ^ Szabó, Jácint (2009)、「ある程度制約されたサブグラフの優れた特徴付け」、Journal of Combinatorial Theory、シリーズB、99 (2): 436– 446、doi : 10.1016/j.jctb.2008.08.009、MR  2482961。
  3. ^ Tutte, WT (1954)、「有限グラフの因子定理の簡潔な証明」、Canadian Journal of Mathematics、6 : 347–352、doi :10.4153/CJM-1954-033-3、hdl : 10338.dmlcz/  101241 、MR0063008。
  4. ^ シプサー、マイケル（1997）、計算理論入門、PWS出版社、p.260。
  5. ^ この縮約については、 Goldreich, Oded (2008)『計算複雑性：概念的視点』Cambridge University Press, Proposition 2.27, p. 81, ISBN 978-4-8522-23313-1に記載されています。 978-1-139-47274-6。
  6. ^ abc Agrawal, Manindra ; Allender, Eric ; Impagliazzo, Russell ; Pitassi, Toniann ; Rudich, Steven (1997)、「縮約の複雑さの軽減」、第29回ACMコンピューティング理論シンポジウム(STOC '97)の議事録、pp.  730– 738、doi : 10.1145/258533.258671、ISBN 0-89791-888-6アグラワル、マニンドラ；アレンダー、エリック；ルディッチ、スティーブン（1998）「回路計算量の削減：同型定理とギャップ定理」、コンピュータとシステム科学ジャーナル、57（2）：127–143、doi：10.1006/jcss.1998.1583。
  7. ^ トレヴィサン、ルカ；ソーキン、グレゴリー・B；スーダン、マドゥ；ウィリアムソン、デビッド・P（2000）「ガジェット、近似、線形計画法」、SIAM Journal on Computing、29（6）：2074– 2097、doi：10.1137/S0097539797328847、MR  1756405。
  8. ^ ガリー、マイケル・R. ;ジョンソン、デビッド・S. ;ストックマイヤー、ラリー(1976)、「いくつかの簡略化されたNP完全グラフ問題」、理論計算機科学、1 (3): 237– 267、doi :10.1016/0304-3975(76)90059-1。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Gadget_(computer_science)&oldid=1287953241"