ガジェット（コンピュータサイエンス）

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

Szabó (2​​009) は、ガジェットの使用をWT Tutteによる1954 年のグラフ理論の論文にまで遡らせている。この論文で Tutte は、与えられた次数の制約を持つサブグラフを見つける問題を完全マッチング問題に簡略化するためのガジェットを提供した。しかし、「ガジェット」という用語はもっと後の時代に生まれたものであり、Tutte の論文には登場しない。^{[2] [3]}

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

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

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

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

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

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

ガジェットの応用例の 1 つは、近似が困難であることがわかっている問題を、困難さが証明される別の問題に縮小することによって、近似結果の困難さを証明することです。この応用例では、通常、目的関数の値にギャップがあり、特定のインスタンスがギャップの低い側にあるか高い側にあるかを判断するのが難しい最初の問題のインスタンスのファミリがあります。これらの証明で使用される縮小、および縮小で使用されるガジェットは、このギャップの存在を維持する必要があり、縮小から得られる近似不可能性の結果の強さは、ギャップがどの程度維持されるかによって異なります。

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 らは、3-SAT を 2-SAT の重み付きバリアント (7 つの重み付き 2-SAT 節で構成) に縮約するための最適なガジェットを提供しています。これは、Garey、Johnson、Stockmeyer (1976) のものよりも強力です。このガジェットを、MAX 2-SAT の既知の半正定値計画近似アルゴリズムとともに使用することで、近似比 0.801 の MAX 3-SAT の近似アルゴリズムを提供し、これは従来のアルゴリズムよりも優れています。