多項式時間削減

計算複雑性理論において、多項式時間縮約とは、ある問題を別の問題を使って解く方法である。ある理論では、2 番目の問題を解く仮想サブルーチンが存在する場合、それを 2 番目の問題の入力に変換または縮約し、そのサブルーチンを 1 回以上呼び出すことで、1 番目の問題を解決できることが示される。1 番目の問題を 2 番目の問題に変換するのに必要な時間と、サブルーチンが呼び出される回数の両方が多項式である場合、1 番目の問題は 2 番目の問題に多項式時間縮約可能である。^[1]

多項式時間簡約は、最初の問題が2番目の問題よりも難しくないことを証明します。なぜなら、 2番目の問題に対して効率的なアルゴリズムが存在する場合は常に、最初の問題に対しても効率的なアルゴリズムが存在するからです。逆説により、最初の問題に対して効率的なアルゴリズムが存在しない場合には、2番目の問題に対しても効率的なアルゴリズムは存在しません。^{[1]多項式時間簡約は、複雑性理論において、}複雑性クラスとそれらのクラスの完全問題の両方を定義するために頻繁に使用されます。

削減の種類

最も一般的な多項式時間縮約の3つのタイプは、最も制限の厳しいものから最も制限の少ないものの順に、多項式時間多対一縮約、真理値表縮約、チューリング縮約である。これらのうち最も頻繁に使用されるのは多対一縮約であり、場合によっては「多項式時間縮約」という語句が多項式時間多対一縮約を意味するために使用されることがある。^[2]最も一般的な縮約はチューリング縮約であり、最も制限の厳しいのは多対一縮約であり、真理値表縮約はその中間を占める。^[3]

多対一削減

問題Aから問題Bへの多項式時間多対一縮約(通常は両方とも決定問題であることが要求される) は、問題Aへの入力を問題Bへの入力に変換し、変換された問題が元の問題と同じ出力を持つようにする多項式時間アルゴリズムである。問題Aのインスタンスx は、この変換を適用して問題Bのインスタンスy を生成し、 y を問題Bのアルゴリズムの入力として与え、その出力を返すことで解決できる。多項式時間多対一縮約は、リチャード・カープにちなんで多項式変換またはカープ縮約とも呼ばれる。このタイプの縮約は、またはで表される。^[4]^[1] $A\leq _{m}^{P}B$ $A\leq _{p}B$

真理値表の縮小

問題Aから問題B (どちらも決定問題)への多項式時間真理値表還元は、問題Aへの入力を問題Bへの固定数の入力に変換し、元の問題の出力をBの出力の関数として表現できる多項式時間アルゴリズムです。 Bの出力をAの出力にマッピングする関数は、すべての入力に対して同じでなければならないため、真理値表で表現できます。このタイプの還元は、式で表すことができます。^[5] $A\leq _{tt}^{P}B$

チューリング還元

問題Aから問題Bへの多項式時間チューリング還元は、問題Bのサブルーチンを多項式回数呼び出し、それらのサブルーチン呼び出し以外では多項式時間を使用して問題Aを解くアルゴリズムです。多項式時間チューリング還元は、スティーブン・クックにちなんでクック還元とも呼ばれます。このタイプの還元は、式と表記される場合があります。^{[4]多対一還元は、問題}Bのサブルーチンの呼び出し回数がちょうど 1 回で、還元によって返される値がサブルーチンによって返される値と同じである、チューリング還元の制限された変種と見なすことができます。 $A\leq _{T}^{P}B$

完全

与えられた複雑性クラスCと簡約 ≤ に対する完全問題とは、 Cに属する問題Pであり、Cのすべての問題Aには簡約A ≤ Pがある。たとえば、問題がNPに属し、NPのすべての問題に多項式時間の多対一簡約がある場合、その問題はNP 完全である。NPに属する問題は、既知のNP完全問題からその問題への単一の多項式時間の多対一簡約を見つけることによってNP完全であることが証明できる。^{[6]多項式時間の多対一簡約は、}PSPACE完全言語やEXPTIME完全言語など、他の複雑性クラスの完全問題を定義するために使用されている。^[7]

P（多項式時間決定問題のクラス）のすべての決定問題は、多項式時間の多対一縮約によって、他のすべての非自明な決定問題（非自明とは、すべての入力が同じ出力を持つわけではないことを意味する）に縮約できる。問題AのインスタンスをBに変換するには、A を多項式時間で解き、その解を使用して、異なる答えを持つ問題Bの 2 つのインスタンスのうち 1 つを選択する。したがって、L、NL、NC、およびP自体などのP内の複雑性クラスでは、多項式時間縮約を使用して完全な言語を定義することはできない。このように使用すると、P内のすべての非自明な問題が完全になってしまう。代わりに、対数空間縮約やNC縮約などのより弱い縮約が、P 完全問題などのこれらのクラスの完全問題のクラスを定義するために使用される。^[8]

複雑性クラスの定義

複雑性クラスNP、PSPACE、およびEXPTIMEの定義には、簡約は含まれません。簡約は、これらのクラスの完全な言語の定義でのみ検討されます。ただし、場合によっては、複雑性クラスが簡約によって定義されることがあります。C が任意の決定問題である場合、となる言語Aで構成される複雑性クラスC を定義できます。この場合、C はCに対して自動的に完全になりますが、C には他の完全な問題も含まれる場合があります。 $A\leq _{m}^{P}C$

一例として、実数の存在理論から定義される計算量クラスが挙げられます。これはNP 困難でPSPACEに属することが知られている計算問題ですが、 NP、PSPACE 、または多項式階層のどの言語に対しても完全であるとは知られていません。は、実数の存在理論への多項式時間多対一還元を持つ問題の集合です。これには、無向グラフの直線交差数を決定するなど、他の完全な問題がいくつかあります。の各問題はPSPACEに属するという性質を継承し、各-完全な問題はNP困難です。^[9] $\exists \mathbb {R}$ $\exists \mathbb {R}$ $\exists \mathbb {R}$ $\exists \mathbb {R}$

同様に、複雑性クラスGI はグラフ同型性問題に還元できる問題から構成される。グラフ同型性はNPと co- AMの両方に属することが知られているため、このクラスのすべての問題に同じことが当てはまる。問題がこのクラスに対して完全であれば、その問題は GI 完全である。グラフ同型性問題自体は GI 完全であり、他のいくつかの関連する問題も同様である。^[10]

参照

カープの21のNP完全問題

外部リンク

MIT OpenCourseWare: 16. 複雑性: P、NP、NP完全性、縮約

参考文献

^ abc クラインバーグ、ジョン;タルドス、エヴァ(2006)。アルゴリズム設計。ピアソン教育。 452–453ページ。ISBN 978-0-321-37291-8。
^ Wegener, Ingo (2005)、複雑性理論：効率的なアルゴリズムの限界を探る、Springer、p. 60、ISBN 9783540274773。
^ Mandal, Debasis; Pavan, A.; Venugopalan, Rajeswari (2014). 最悪ケース困難性仮説における Cook 完全性と Karp-Levin 完全性の分離。第 34 回ソフトウェア技術と理論計算機科学の基礎に関する国際会議。ISBN 978-3-939897-77-4。
^ ab Goldreich, Oded (2008)、計算複雑性：概念的観点、ケンブリッジ大学出版局、pp. 59–60、ISBN 9781139472746
^ Buss, SR ; Hay, L. (1988)、「真理値表の SAT への還元可能性と NP 上の差分階層について」、第 3 回複雑性理論構造会議の議事録、pp. 224–233、CiteSeerX 10.1.1.5.2387、doi :10.1109/SCT.1988.5282、ISBN 978-0-8186-0866-7。
^ ガリー、マイケル・R. ;ジョンソン、DS (1979)、コンピュータと扱いにくさ：NP完全性理論へのガイド、WHフリーマン。
^ Aho, AV (2011)、「複雑性理論」、Blum, EK; Aho, AV (編)、コンピュータサイエンス: ハードウェア、ソフトウェア、そしてその中心、pp. 241–267、doi : 10.1007/978-1-4614-1168-0_12、ISBN 978-1-4614-1167-3特に255ページを参照。
^ グリーンロー、レイモンド、フーバー、ジェームズ、ルッツォ、ウォルター (1995)、「並列計算の限界、P-完全性理論」、ISBN 978-0-19-508591-4特に、P のすべての非自明な問題は、他のすべての非自明な問題に対して多項式時間の多対一還元を持つという議論については、48 ページを参照してください。
^ Schaefer, Marcus (2010)、「いくつかの幾何学的および位相的問題の複雑性」(PDF)、グラフ描画、第 17 回国際シンポジウム、GS 2009、シカゴ、イリノイ州、米国、2009 年 9 月、改訂版論文、Lecture Notes in Computer Science、vol. 5849、Springer-Verlag、pp. 334–344、doi : 10.1007/978-3-642-11805-0_32、ISBN 978-3-642-11804-3。
^ ヨハネス・ケブラー;シェーニング, ウーヴェ;トラン、ヤコボ (1993)、「グラフ同型問題: その構造的複雑性」、Birkhäuser、ISBN 978-0-8176-3680-7、OCLC 246882287。

[kleinberg-tardos-1] クラインバーグ、ジョン;タルドス、エヴァ(2006)。アルゴリズム設計。ピアソン教育。 452–453ページ。ISBN 978-0-321-37291-8。

[2] Wegener, Ingo (2005)、複雑性理論：効率的なアルゴリズムの限界を探る、Springer、p. 60、ISBN 9783540274773。

[mandal2014-3] Mandal, Debasis; Pavan, A.; Venugopalan, Rajeswari (2014). 最悪ケース困難性仮説における Cook 完全性と Karp-Levin 完全性の分離。第 34 回ソフトウェア技術と理論計算機科学の基礎に関する国際会議。ISBN 978-3-939897-77-4。

[goldreich-4] Goldreich, Oded (2008)、計算複雑性：概念的観点、ケンブリッジ大学出版局、pp. 59–60、ISBN 9781139472746

[5] Buss, SR ; Hay, L. (1988)、「真理値表の SAT への還元可能性と NP 上の差分階層について」、第 3 回複雑性理論構造会議の議事録、pp. 224–233、CiteSeerX 10.1.1.5.2387、doi :10.1109/SCT.1988.5282、ISBN 978-0-8186-0866-7。

[6] ガリー、マイケル・R. ;ジョンソン、DS (1979)、コンピュータと扱いにくさ：NP完全性理論へのガイド、WHフリーマン。

[7] Aho, AV (2011)、「複雑性理論」、Blum, EK; Aho, AV (編)、コンピュータサイエンス: ハードウェア、ソフトウェア、そしてその中心、pp. 241–267、doi : 10.1007/978-1-4614-1168-0_12、ISBN 978-1-4614-1167-3特に255ページを参照。

[8] グリーンロー、レイモンド、フーバー、ジェームズ、ルッツォ、ウォルター (1995)、「並列計算の限界、P-完全性理論」、ISBN 978-0-19-508591-4特に、P のすべての非自明な問題は、他のすべての非自明な問題に対して多項式時間の多対一還元を持つという議論については、48 ページを参照してください。

[9] Schaefer, Marcus (2010)、「いくつかの幾何学的および位相的問題の複雑性」(PDF)、グラフ描画、第 17 回国際シンポジウム、GS 2009、シカゴ、イリノイ州、米国、2009 年 9 月、改訂版論文、Lecture Notes in Computer Science、vol. 5849、Springer-Verlag、pp. 334–344、doi : 10.1007/978-3-642-11805-0_32、ISBN 978-3-642-11804-3。

[10] ヨハネス・ケブラー;シェーニング, ウーヴェ;トラン、ヤコボ (1993)、「グラフ同型問題: その構造的複雑性」、Birkhäuser、ISBN 978-0-8176-3680-7、OCLC 246882287。