NP困難およびNP完全クラス

それがNPにあり、次のようになっている場合、問題はクラスNPCにあります hardNPの問題として。問題はNP-hard NP自体に問題がない場合でも、NPのすべての問題が多項式時間で削減できる場合。

これらの問題のいずれかに多項式時間アルゴリズムが存在する場合、NPのすべての問題は多項式時間で解決できます。これらの問題はNP-complete。NP完全性の現象は、理論的理由と実際的理由の両方で重要です。

NP完全性の定義

言語 B です NP-complete 2つの条件を満たす場合

B NPにあります
すべて A NPでは、多項式時間は次のように還元できます。 B。

言語が2番目のプロパティを満たしているが、必ずしも最初のプロパティを満たしているとは限らない場合、その言語は B として知られている NP-Hard。非公式に、検索問題B です NP-Hard 存在する場合 NP-Complete 問題 A チューリングは B。

NP困難の問題は、多項式時間で解決することはできません。 P = NP。問題がNPCであることが判明した場合、そのための効率的なアルゴリズムを見つけるために時間を無駄にする必要はありません。代わりに、設計近似アルゴリズムに焦点を当てることができます。

NP完全問題

以下は、多項式時間アルゴリズムが知られていないいくつかのNP完全問題です。

グラフにハミルトン閉路があるかどうかの判断
ブール式が充足可能かどうかの判断など。

NP困難な問題

次の問題はNP困難です

回路の満足度の問題
セットカバー
頂点被覆
巡回セールスマン問題

これに関連して、TSPはNP完全であると説明します

TSPはNP完全です

巡回セールスマン問題は、セールスマンと一連の都市で構成されます。セールスマンは、特定の都市から始まり、同じ都市に戻る各都市を訪問する必要があります。問題の課題は、巡回セールスマンが旅行の全長を最小限に抑えたいということです。

証明

証明する TSP is NP-Complete、最初にそれを証明する必要があります TSP belongs to NP。TSPでは、ツアーを見つけて、ツアーに各頂点が1回含まれていることを確認します。次に、ツアーの端の総コストが計算されます。最後に、コストが最小かどうかを確認します。これは、多項式時間で完了することができます。したがって、TSP belongs to NP。

第二に、それを証明する必要があります TSP is NP-hard。これを証明するための1つの方法は、Hamiltonian cycle ≤_p TSP （ハミルトン閉路問題はNP完全であることがわかっているため）。

仮定する G = (V, E) ハミルトン閉路のインスタンスになります。

したがって、TSPのインスタンスが構築されます。完全グラフを作成しますG^' = (V, E^')、どこ

$$ E ^ {'} = \ lbrace（i、j）\ Colon i、j \ in V \：\：and \：i \ neq j $$

したがって、コスト関数は次のように定義されます。

$$ t（i、j）= \ begin {cases} 0＆if \ ：（ i、j）\：\ in E \\ 1＆else \ end {cases} $$

ここで、ハミルトン閉路を仮定します h に存在します G。の各エッジのコストは明らかですh です 0 に G^' 各エッジが属するので E。したがって、h のコストがあります 0 に G^'。したがって、グラフの場合G ハミルトン閉路があり、グラフ G^' のツアーがあります 0 費用。

逆に、 G^' ツアーがあります h^' せいぜいコストの 0。のエッジのコストE^' です 0 そして 1定義により。したがって、各エッジには次のコストが必要です。0 のコストとして h^' です 0。したがって、次のように結論付けます。h^' のエッジのみが含まれます E。

したがって、私たちはそれを証明しました G ハミルトン閉路がある場合に限り G^' せいぜい費用のツアーがあります 0。TSPはNP完全です。