30

NP-Complete のウィキペディアのエントリから:

「いくつかの新しい問題が NP 完全であることを証明する最も簡単な方法は、最初にそれが NP であることを証明し、次に既知の NP 完全問題をそれに還元することです。」

私はこれを理解していると確信しています: 問題がある場合、次の場合にそれが NP-Complete であることを示すことができます:

  1. NP であることを示します (問題の解は、非決定論的チューリング マシンで多項式時間で検証できます)。

  2. すでに NP 完全であることがわかっている問題を新しい問題に「還元」できることを示す

では、私の質問は、最初の NP 完全問題がどのようにして NP 完全であることが「証明」されたのかということです。かつて、既知の NP 完全問題のセットはゼロであったに違いありません。これにより、上記のプロセスのステップ 2 に頼ることができなくなります。

これは、私が気付いていない証明のための別の方法があると私に思わせます。それか、既知の多項式時間解がないために、NP完全なプロパティ全体が特定の問題に対して「想定」されている可能性があります。（実際、これを書いたので、そうであっても驚かないでしょうが、いずれにせよ、グルのフィードバックが欲しいです）。

4

2 に答える 2

32

クックの定理

クラス NP は、非決定論的チューリング マシンによって多項式時間で決定可能な問題のクラスとして定義できます。この定理は、非決定論的チューリング マシンの操作をブール式でエンコードすることにより、 SAT が NP 完全であることを示しています。この方法では、その式が SATisfiable である場合にのみマシンが受け入れます。

歴史的に言えば、NP完全性の概念は、Richard Karpの影響力のある論文( Reducibility Among Combinatorial Problems )で導入されました。そこで彼はNP完全性を定義し、クックの定理を使用し、1回のビッグショットで21の問題がNP完全であることを証明しました。

于 2008-11-20T18:08:41.370 に答える
5

証明の本質を説明すると (これは、Garey & Johnson のComputers and Intractibilityの数ページにわたる困難な作業です):

あらゆる計算問題は、チューリング マシンとして表現できます。

チューリング マシンは、特定の複雑さの制約を満たす論理問題として表現できます。

したがって、論理問題を多項式時間で解くことができれば、チューリング マシンの問題を多項式時間で解くことができます。

これは (他のいくつかの考慮事項と共に)、多項式時間で論理問題を解くことができれば、任意の NP 問題を多項式時間で解くことができることを示しています。これが NP 完全の定義であるため、論理問題は NP 完全であり、他の問題の基礎として使用できます。

使用される論理問題は、充足可能性 (しばしば SAT と略される) と呼ばれます。(A or not-B or not-C) の形式の一連の節 (任意の数の命題と、論理和で接続された命題の否定からなる節) が与えられたとき、すべて条項は本当ですか？

NP 完全性は明確に定義されたプロパティです。問題が NP 完全であることに疑問を抱く唯一の理由は、別の NP 完全問題をその問題に還元できると考えたが、便利な問題を見つけたり、証明を導き出すことができなかったからです。

問題は、NP 完全問題が存在するかどうか、または問題が NP 完全であることをどのように証明するかではなく、それが何を意味するかです。NP 完全問題を解くための多項式時間アルゴリズムを作成した人はまだ誰もいませんし、そのようなアルゴリズムが存在しないことを証明した人もいません。P=NP であるかどうかにかかわらず、NP 完全問題を解決するための優れたアルゴリズムはありません。

これはクレイプール財団のミレニアム問題の 1 つであり、非常に優秀な人々を何年も逃してきた証拠を見つけることができれば、100 万ドルの価値があります。

于 2008-11-20T18:29:51.390 に答える