Loading article…
計算複雑性理論では、非決定性多項式時間で解けるあらゆる問題Lに対して、 LからHへの多項式時間縮約が存在する場合、計算問題HはNP 困難であると呼ばれる。つまり、 Hの解が1 単位時間かかると仮定すると、Hの解はL を多項式時間で解くのに使用できる。[1] [2]結果として、単一の NP 困難問題を解く多項式時間アルゴリズムを見つけることは、複雑性クラスNPのすべての問題に対する多項式時間アルゴリズムを与えることになる。 P≠NPであると疑われているが証明されていないため、NP 困難問題に対する多項式時間アルゴリズムが存在する可能性は低い。[3] [4]
NP 困難問題の簡単な例としては、部分集合の合計問題があります。
非公式には、HがNP困難であれば、少なくともNPの問題と同じくらい解くのが難しいということです。しかし、逆は当てはまりません。いくつかの問題は決定不可能であり、したがってNPのすべての問題よりもさらに解くのが困難ですが、それらはおそらくNP困難ではありません（P=NPでない限り）。[5]
意味
決定問題 HがNP 困難であるとは、 NP に属するすべての問題Lに対して、 LからHへの多項式時間の多項式還元が存在する場合を言う。[1] : 80
もう1つの定義は、 NP完全問題GからHへの多項式時間簡約が存在することを要求するものである。[1] : 91 NP における任意の問題L は多項式時間でGに簡約されるため、L は多項式時間でHに簡約されるため、この新しい定義は前の定義を意味する。これは NP 困難クラスを決定問題に限定せず、探索問題や最適化問題も含む。
結果
P ≠ NP の場合、NP 困難な問題は多項式時間で解決できません。
いくつかのNP困難な最適化問題は、一定の近似比（特にAPXのもの）または任意の近似比（PTASまたはFPTASのもの）まで多項式時間で近似することができます。近似可能性には多くのクラスがあり、それぞれが異なるレベルまでの近似を可能にします。[6]
例
すべてのNP完全問題はNP困難でもあります（NP完全問題の一覧を参照）。たとえば、重み付きグラフのすべてのノードを通る最小コストの巡回ルートを見つける最適化問題（一般に巡回セールスマン問題として知られています）はNP困難です。[7]部分集合の合計問題は別の例です。整数の集合が与えられたとき、それらの空でない部分集合の合計はゼロになりますか？これは決定問題であり、たまたまNP完全です。
NP 困難だがNP 完全ではない決定問題、例えば停止問題があります。これは、「プログラムとその入力が与えられた場合、それは永遠に実行されるか?」を問う問題です。これはyes / no の質問であり、決定問題でもあります。停止問題が NP 困難だが NP 完全ではないことは簡単に証明できます。たとえば、ブール値の充足可能性問題は、すべての真理値の割り当てを試し、式を満たすものを見つけたら停止し、そうでない場合は無限ループに入るチューリングマシンの記述に変換することで、停止問題に還元できます。NP のすべての問題は有限回数の操作で決定可能であるため、停止問題がNPに属さないことも簡単にわかりますが、停止問題は一般に決定不可能です。NP完全でも決定不可能でもない NP 困難問題もあります。例えば、真に量化されたブール式の言語は多項式空間では決定可能であるが、非決定性多項式時間では決定可能ではない（NP = PSPACEでない限り）。[8]
NP命名規則
NP 困難な問題は、計算量クラス NP の要素である必要はありません。NP は計算量において中心的な役割を果たすため、いくつかのクラスの基礎として使用されます。
- NP
- 任意のyes解が決定論的チューリングマシンによって多項式時間で解として検証できる（または非決定論的チューリングマシンによって多項式時間で解決できる）計算決定問題のクラス。
- NP困難
- NP の最も難しい問題と少なくとも同じくらい難しい問題のクラス。NP 困難な問題は NP の要素である必要はなく、実際には決定可能ではない場合もあります。
- NP完全
- NP の最も難しい問題を含む決定問題のクラス。各 NP 完全問題は NP に含まれていなければなりません。
- NP簡単
- NP と同じくらい難しいですが、必ずしも NP である必要はありません。
- NP相当
- NP 困難かつ NP 容易であるが、必ずしも NP ではない決定問題。
- NP中間体
- P と NP が異なる場合、NP の領域には、P と NP 完全問題の間に入る決定問題が存在します。(P と NP が同じクラスである場合、NP 中間問題は存在しません。この場合、すべての NP 完全問題は P に含まれ、定義により、NP のすべての問題は NP 完全問題に縮小できるためです。)
応用分野
NP 困難な問題は、次のような分野でルールベースの言語を使用して解決されることがよくあります。
参照
参考文献
- ^ abc Leeuwen, Jan van編 (1998).理論計算機科学ハンドブック. 第A巻, アルゴリズムと複雑性. アムステルダム: Elsevier. ISBN 0262720140. OCLC 247934368.
- ^ Knuth, Donald (1974). 「NP困難問題に関する追記」ACM SIGACT News . 6 (2): 15– 16. doi :10.1145/1008304.1008305. S2CID 46480926.
- ^ ダニエル・ピエール・ボヴェ;ピエルイジ・クレッシェンツィ (1994)。複雑性の理論の紹介。プレンティス・ホール。 p. 69.ISBN 0-13-915380-2。
- ^ 「Shtetl-Optimized » Blog Archive » P≠NPの科学的根拠」www.scottaaronson.com 。 2016年9月25日閲覧。
- ^ 「決定不能(R の補集合) は NP 困難のサブセットか?」Computer Science Stack Exchange 。 2024 年 2 月 9 日閲覧。
- ^ Escoffier, B.; Paschos, B.Th. (2010). 「近似クラスの構造に関する調査」.コンピュータサイエンスレビュー. 4 (1): 19– 40.
- ^ Lawler, EL ; Lenstra, JK ; Rinnooy Kan, AHG; Shmoys, DB (1985)、『巡回セールスマン問題：組み合わせ最適化のガイドツアー』、John Wiley & Sons、ISBN 0-471-90413-9。
- ^ より正確には、この言語はPSPACE 完全です。たとえば、Wegener, Ingo (2005)、Complexity Theory: Exploring the Limits of Efficient Algorithms、Springer、p. 189、ISBN を参照してください。 9783540210450。
- ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論ガイド。数学科学シリーズ (第 1 版)。ニューヨーク: WH フリーマン アンド カンパニー。ISBN 9780716710455. MR 0519066. OCLC 247570676.