NP完全性と計算困難性

NP完全性は、NPクラスの中で最も困難な問題、すなわちNP内のすべての問題が帰着される問題を特定し、効率的なアルゴリズムが知られていない、または存在しない可能性が高い問題を認識するための標準的な枠組みを提供します。

Definition

決定問題がNP完全であるとは、それがNPに属し（そのyes-インスタンスが効率的に検証可能な証明を持つ）、かつNP内のすべての問題が多項式時間でそれに帰着される場合を指します。このような問題はNP内で最も困難であり、いずれか1つに対して多項式時間アルゴリズムが存在すれば、すべての問題に対してそれが得られることになります。

Scope

このトピックでは、複雑性クラスPとNP、多項式時間帰着、NP困難性とNP完全性の定義、充足可能性問題をNP完全であると確立したCook-Levinの定理、KarpによるNP完全問題のカタログ、およびアルゴリズム設計における計算困難性の実際的な影響について扱います。これらの概念を困難な問題の認識と対処に適用します。計算複雑性クラスのより広範な形式理論は、計算理論のサブフィールドで扱われます。

Core questions

• 複雑性クラスPとNPを区別するものは何ですか？
• 多項式時間帰着は、ある問題から別の問題へどのように困難性を伝達しますか？
• Cook-Levinの定理は何を確立し、充足可能性が中心であるのはなぜですか？
• 既知のNP完全問題からの帰着によって、新しい問題がNP完全であるとどのように証明されますか？
• 問題がNP困難であると示された後、どのようなアルゴリズム戦略が残されていますか？

Key concepts

• 複雑性クラスP
• 複雑性クラスNP
• 多項式時間帰着
• NP困難性
• NP完全性
• Cook-Levinの定理
• ブール充足可能性問題 (SAT)
• P対NP問題

Key theories

Cook-Levinの定理

Cook-Levinの定理は、ブール充足可能性問題 (SAT) がNP完全であることを証明しています。NP内のすべての問題が多項式時間でSATに帰着されるため、これは最初のNP完全問題となり、他の問題の困難性を証明するための基礎を提供しました。

組み合わせ問題間の帰着可能性

Karpは、多項式時間帰着が、クリーク、頂点被覆、ハミルトン閉路、分割などの多くの自然な問題をNP完全問題の網の目状に結びつけ、それによって各問題が他の問題からの帰着によって困難であることを証明できることを示しました。

Clinical relevance

問題がNP完全であることを認識することは、計算分野において最も実用的に有用な結果の1つです。これは、エンジニアに高速な厳密アルゴリズムを期待しないよう促し、代わりに近似アルゴリズム、ヒューリスティクス、典型的なインスタンスに調整された厳密ソルバー、または扱いやすい特殊ケースへの制限を展開するよう促します。多くのスケジューリング、ルーティング、パッキング、および設計問題はNP完全です。

History

Stephen Cookは1971年にNP完全性を導入し、SATがNP完全であることを証明しました。Leonid Levinは独立して同様の結果に到達しました。Richard Karpの1972年の論文は、21の自然な問題がNP完全であることを示し、この枠組みの適用範囲を確立しました。GareyとJohnsonの1979年の著書は、数百のNP完全問題をカタログ化し、標準的な参考文献となりました。

Debates

P対NP問題

PとNPが等しいか否か、すなわち、効率的に検証可能なすべての問題が効率的に解けるか否かは、この分野における最も重要な未解決問題です。ほとんどの研究者はPとNPは等しくないと推測していますが、この問題は未解決であり、ミレニアム懸賞問題の1つです。

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

NP困難とNP完全の違いは何ですか？

問題がNP困難であるとは、NP内のすべての問題が多項式時間でそれに帰着されることを意味しますが、それ自体がNPに属する必要はなく、決定問題である必要もありません。問題がNP完全であるとは、それがNP困難であり、かつNPに属する場合を指します。NP完全問題は、NPに属する問題の中で最も困難な問題です。

NP完全性とは、問題が決して解けないことを意味しますか？

いいえ、そうではありません。これは、すべての入力に対して多項式時間アルゴリズムが知られておらず、PとNPが等しくない場合、そのようなアルゴリズムが存在しない可能性が高いことを意味します。実際には、このような問題は、近似アルゴリズム、ヒューリスティクス、現実的なインスタンスで機能する指数時間ソルバー、または特殊なケースに限定することによって対処されます。