NP削減の多項式ランタイムを決定する方法は？

Question

NPの問題がNPコンプリートであることを示すには、$ l leq_ {p} l '$を示す必要があります。私が混乱しているのは、CLRのすべてのNP不完全な問題で、$ L $の削減アルゴリズムを$ L '$に変換するだけで多項式であると述べることです。そのようなクリークやハムサイクルのような問題の例を提供したのは、それが多項式時間であることをどのように証明できますか？

Answer 1

ここでの問題は、削減のポイントの誤解です。 NPコンプリートの問題は、多項式時間アルゴリズムを持つことが知られていません。もしそうなら、p $ = $ np、そうでない場合はp $ neq $ np-これは 大きい 理論的なコンピューターサイエンスの質問。

あなたが見ている削減のポイントは、問題$ l '$がNP不完全であり、少なくともNPの他のものと同じくらい難しいことを示すことです。これは、多項式時間で$ l '$を解くことができれば、削減を使用して多項式時間で$ l $を解くことができることを実証することでこれを行います（$ l $のインスタンスを取り、$ l'のインスタンスに変換することができます。 $、それを解決してから、そのソリューションを使用して、元のインスタンスのソリューションを取得します）。

$ l $はnp完全であるため、これはまた、多項式時間に解決できれば解決できることを意味します 毎日 多項式時間のNPの問題（したがって、NP不完全な問題は、ある意味でNPの「最も難しい」問題であるという直感）。

その上にいくつかの技術的なビットを追加するために、問題$ pi $は次の場合にnp完全です。

1. $ pi in $ np、および
2. $ pi $はnp-hardです。

問題$ pi $はnpにあります。入力のサイズの多項式時間で$ pi $を解く非決定的アルゴリズムがある場合、または同等に$ pi $ inのインスタンスへの回答を確認できます。 決定論的 多項式時間。

問題$ pi $はnp-hardです 毎日 問題$ phi in $ npには、$ phi leq_ {p} pi $（これは$ phi $ごとに異なる削減になる可能性がある）の多項式時間削減が存在します。実際に私たちがしていることは、実際にこれらの削減を一緒に連鎖させることですので、NPハードの問題$ pi '$があると言って、NPのすべてからの減少があることを知っているので、$ pi'を示すことができれば leq_ {p} pi $次に、削減を作成することにより、$ pi $にすべての削減があることを示すことができます（$ pi '$を介して進みます）。

ですから、元の質問に戻るために、$ l '$の多項式時間アルゴリズムがあるかどうかはわかりません - ほとんどの人はおそらくそうではないと思うでしょう。 NP不完全な問題のために1つの多項式時間アルゴリズムを見つけようとしていますが、これまでのところ運がありませんでした（もちろん、それらのいずれかのこのようなアルゴリズムは、の多項式時間アルゴリズムを意味します。 すべての np）。削減「Just」は、$ l '$がこれらの難しい問題の1つであることを示しています。