P = NP の明確化

Question

もっと単純で分かりやすい例があると思わない限り、巡回セールスマンを例として使用してみましょう。

P=NP の問題についての私の理解は、難しい問題の最適解が与えられた場合、答えを確認するのは簡単ですが、解を見つけるのは非常に難しいということです。

巡回セールスマンでは、最短ルートが与えられたとしても、ソリューションが最適であることを確認するためにすべてのルートを計算する必要があるため、それが最短ルートであることを判断することは同様に困難です。

それは意味がありません。それで、私には何が欠けているのでしょうか？このことについて学ぶときに、他の多くの人も同様の理解上の誤りに遭遇すると思います。

Answer 1

あなたのバージョンのTSPは実際にはnp-hardです。それが正しい解決策であることを確認するのは難しいです。NP-CompleteのTSPのバージョンは、問題の決定版（ウィキペディアの引用符）：

TSPの決定版（長さLが与えられた場合、タスクはグラフが持つかどうかを決定することです。ほとんどのL）のツアーは、NP完全な問題のクラスに属しています。

言い換えれば、「TSPグラフを通して可能な限り最短のルートと尋ねる代わりに、「予算内に収まるTSPグラフを通る経路はありますか」と尋ねています。

Answer 2

ここではまれな答えがたくさんありますが、あなたが持っているように思われるカップルのかなり重要な誤解を明確にしていません。

PとNPの両方が、「決定問題」と呼ばれるもののクラスです。これらは答えがイエスかノーの問題です。 （より正式に彼らはすべての文字列と言語のすべての質問です。その言語の文字列ですが、それが重要な区別ではありません）。この意味で、あなたは「難しい問題の最適な解決策を考えると、答えを確認するのは簡単であるが、解決策を見つけるのは非常に困難であることは、最適な解決策を持っていないので、解決策を見つけるのは非常に困難である」と言うとき、あなたはあなたの理解にわずかに間違っている。 ""解決策を「評価」できる問題であり、「最善の」解決策は最適化の問題であり、そのうち走行セールスマン問題は一例である。この最適化問題のインスタンスと整数kを考えると、問題を考慮して最適化問題を決定的問題に変えることができます。問題は、客観的な値がkより優れている解決策がありますか？ "

もう一つのことは、NPの意味について少し混乱している可能性があります。 Pは多項式時刻で解決できる決定問題のクラスです（理解しているようです）。 NPは「決定論的多項式時間」を表し、それは問題のインスタンスがいくつかの追加情報を考えると、問題のインスタンスがYESに与えるかどうかを簡単に確認できる問題のクラスです。だから私達のTSPの問題を見て、私がTSPのインスタンスを持っていた場合、そして総費用がk未満の解決策であれば、解決策が本当に解決策であり、そのコストがk未満であることを簡単に確認することができます。そのため、TSPに関連する決定問題はNPにあります。しかし、NPのすべての問題が「難しい」ではありません。実際にPはNPのサブセットですが、決定問題を簡単に解決できる場合は、インスタンスがそれを解くだけでYes Ant回答が表示されているかどうかを簡単に確認できます。

しかし、私たちが解決するのが難しいと思うNPにはいくつかの問題があります。少しずれて、これらのNP完全な問題を呼び出します。 （これらはまだ決断問題でなければなりません）。問題Aが少なくとも問題と同じくらい難しいと言えるのは、問題を解決するブラックボックスオラクルがあると仮定すると、問題を効率的に解決するために使用することができます。また、TSPの例をもう一度考えてみましょう。明らかに、最適化の問題を解決することができた場合（それは最適な解決策を取得）、あなたは決定問題を解決することができます。そのため、最適化の問題は少なくとも対応する決定問題と同じくらい困難です。 TSPの決定問題版がNP完全だったことを示した場合は、最適化問題TSPがNP完全な問題と同じくらい困難であることを知っていますが、それ自体は実際にはNP完了ではありません。決定問題です。私たちはそのような問題をNP-Hardに呼び出します。

Answer 3

$ p $ と $ np $ は、決定問題のクラスです。決定問題のためのアルゴリズムの結果は、「はい」または「いいえ」のいずれかである。 $ p $ の問題でも、そのような回答は迅速な検証につながることはできません。

TSPの決定問題バージョンのインスタンスは、都市と介入の距離の集まりを考えると、 $ k $ より少ない合計長のツアーがありますか？ " $ k $ は、インスタンスで指定された定数です。結果は「はい」または「いいえ」です。どちらの場合も、答えは答えの正確さの迅速な検証につながります。

あなたが尋ねる約束はこれです：特定の提案されたツアー、多項式の時間があることがあることを考える：

• 実際に提案されたツアーがすべての都市を訪問し、存在するインターシティルートを訪問する（時には「有限距離を持つ」とは、長さ $ \ infty $ ）
• もしそうであれば、問題インスタンス内の定数 $ k $ より短いことを決定します。

「はい」または「いいえ」の答えは提案されたツアーを提供します。

使用している $ np $ のモデルの値は、それがソルバーを作るために をエンコードすることです。可能なツアー（通常は繰り返し上回るために大きなセット）がツアーかどうかを確認し、その長さが $ の場合は確認してください。もしそうなら、「はい」を報告してください。 「はい」を報告せずに可能なツアーのコレクションを使い果たした場合は、「いいえ」を報告してください。

このモデルは、早送りの難しさがではないことを示すことを示唆しています。高速解決策の難しさは、検索するために潜在的なツアーが多すぎることです。したがって、私たちが本当にいくつか見つかることができるならば、私たちの検索を小さなサブセットのみに制限するための本当にスマートな方法が潜在的なツアーのコレクションを制限するために、 $ np $ 問題

ソートされたリスト内のバイナリ検索は、Logarithmally only（リストの長さ）の比較ではなく、単一の比較ではなく比較するリストを検索するスマートな方法がある例です。この観点から、TSPの問題は、可能なすべてのTSP問題インスタンスの提案されたツアーを検索するための実質的に速い方法を知らないので困難です。

Answer 4

NPは、決定問題についてのすべてです。回答が「はい」または「いいえ」の問題です。

問題は、答えが「はい」の場合すべてのインスタンスについて、答えが「はい」であることを簡単に証明しましょうヒントがあります。答えが「いいえ」であるインスタンスについては何も言わない。彼らは解決するのが難しいかもしれません。

古典的な走行セールスマンの問題は、都市とその距離のセットを考えると、kより短いツアーを見つけることが可能ですか？そして明らかに、答えがイエスであれば、そのようなツアーが存在し、答えを簡単に表示するためのヒントとしてそれを使用することができます。答えがいいえであれば、誰もそれを証明するようにしてもまだヒントを思い付いていません。

あなたは「推測セールスマン」の問題も言った問題を述べたが、実際には違います。あなたは尋ねます：一連の都市と彼らの距離とツアーを考えると、それが最短ツアーをツアーにするのですか？この場合、答えが「いいえ」の場合、ツアーが短くなり、答えを簡単に表示するためのヒントとして使用することができます。それはNPの反対側です。旅行セールスマンの問題のあなたの代替バージョンは、答えが「いいえ」の場合のすべてのインスタンスの場合、答えを簡単に証明できるヒントがあります。それはNPの正確な反対であるため、このクラスは「CO-NP」と呼ばれます。

そのような多くの問題があります。 NPのすべての問題について、あなたは質問をすることができます： "問題の問題のこの例の答え 'no'"、そしてもちろん回答は正反対の問題の反対です。あなたは、「旅行」と「セールスマン」という言葉ですべての問題が同じ問題であると思考の間違いをしました。

Answer 5

を使うのが一番分かりやすいと思います 3-SAT NP-完了 問題：

がある $n$ ブール変数を使用し、それぞれに次のいずれかを設定するかを決定できます。 $本当$ または $false$ 価値があり、あなたに与えられる $k$ 条項。各句には、次のような 3 つの変数とそれらに対する制約が含まれています。 $(true OR false OR true)$, したがって、最初の変数が true に設定されるか、2 番目の変数が false に設定されるか、または 3 番目の変数が true に設定される場合、この条件は満たされます。の $k$ klauses には、次の 3 つの可能なすべての組み合わせを含めることができます。 $n$ すべての句が満たされるように、各変数にどのような値を設定するかを決定する必要があります。

すべての節が満たされるようにすべての変数の値の組み合わせを見つけた場合、すべての節を一度調べてテストするだけでその組み合わせを非常に簡単に検証できますが、すべての節を満たす組み合わせを見つけるのは非常に難しい場合があります。 。