NP完全性と還元

NP完全問題は、NPクラスの中で最も難しい問題の一つであり、NPのあらゆる問題が効率的にそれに還元されるため、単一のNP完全問題を迅速に解決できれば、すべてのNP問題を解決できることになる。

Definition

問題がNP完全であるとは、それがNPに属し、NP内のすべての問題が多項式時間還元によってそれに還元される場合を指す。このような問題は、NPのメンバーの中で最大に困難であり、効率的な変換によって互いに等価である。

Scope

このトピックでは、多項式時間で検証可能な問題のクラスNP、多項式時間多対一還元、充足可能性をNP完全と確立するクック-レビン定理、カープのNP完全組み合わせ問題のカタログ、および既知の問題からの還元によって新しい問題がNP完全であることを証明する方法論について扱う。

Core questions

• 問題がNPの中で最も難しいものの一つであるとはどういう意味か？
• クック-レビン定理はどのようにして最初のNP完全問題を特定するのか？
• 新しい問題がNP完全であることを証明するために、還元はどのように使用されるのか？
• ある問題のNP完全性が、なぜ他の何千もの問題に影響を与えるのか？

Key theories

クック-レビン定理

ブール充足可能性はNP完全である。なぜなら、任意の多項式時間検証者の計算は充足可能性インスタンスとして符号化でき、他の問題が導出される基礎的な完全問題を提供するからである。

カープ還元とNP完全問題の網

カープは、グラフ彩色から巡回セールスマン決定問題まで、21の自然な問題が多項式時間還元によってNP完全であることを示し、還元という拡大するネットワークを通じて困難性を確立する実践を開始した。

Clinical relevance

NP完全性は、手に負えない問題の実用的な診断基準である。スケジューリング、ロジスティクス、設計、または検証における問題がNP完全であることが示されると、エンジニアは保証された高速な厳密解アルゴリズムを追求するのをやめ、近似アルゴリズム、ヒューリスティクス、整数計画ソルバー、または問題を扱いやすくする制約へと移行する。

History

クックは1971年に充足可能性がNP完全であることを証明し、レヴィンはソビエト連邦で独立して同等の結果を得た。1972年、カープはさらに21のNP完全問題を示し、この現象の普及を明らかにし、NP完全性を計算困難性を診断するための中心的なツールとした。

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

NPは何の略ですか？

NPは非決定性多項式時間（nondeterministic polynomial time）を意味します。同等に、問題がNPに属するのは、提案された解決策が多項式時間でチェック可能である場合であり、たとえそれを見つけるのが困難に見えてもです。与えられた長さ以下の巡回セールスマンの経路は、一度与えられれば検証は容易ですが、発見は明らかに困難です。

新しい問題がNP完全であることをどのように証明しますか？

2つのことを示す必要があります。1つは、その問題がNPに属し、候補解が迅速にチェック可能であること。もう1つは、既知のNP完全問題のいくつかが多項式時間でそれに還元されることです。この還元は既知の困難性を転送し、新しい問題をNPの中で最も難しいものの一つに位置づけます。