Design-and-analysis-of-algorithms-np-hard-complete-classes
NPハードクラスとNP完全クラス
問題は、NPにあり、NPの問題と同様に*困難*である場合、クラスNPCにあります。 NP内のすべての問題が、NP自体に存在しない場合でも、NP時間の多項式時間還元可能であれば、問題は* NP困難*です。
これらの問題のいずれかに多項式時間アルゴリズムが存在する場合、NPのすべての問題は多項式時間で解決可能になります。 これらの問題は NP-complete と呼ばれます。 NP完全性の現象は、理論的および実用的な理由の両方で重要です。
NP完全性の定義
言語 B は、2つの条件を満たす場合、 _ NP-complete_ です。
- B はNPにあります
- NPのすべての A は、 B に還元可能な多項式時間です。
言語が2番目のプロパティを満たしているが、必ずしも最初のプロパティを満たしているわけではない場合、言語 B は NP-Hard として知られています。 非公式には、チューリングが B に還元する* NP-完全*問題 A が存在する場合、検索問題 B は* NP-ハード*です。
NPハードの問題は、 P = NP になるまで、多項式時間で解決できません。 問題がNPCであることが判明した場合、そのための効率的なアルゴリズムを見つけるために時間を浪費する必要はありません。 代わりに、設計近似アルゴリズムに焦点を当てることができます。
NP完全問題
以下は、NP時間問題の一部であり、多項式時間アルゴリズムは知られていません。
- グラフにハミルトニアンサイクルがあるかどうかを判断する
- ブール式が充足可能かどうかの判定など。
NPハード問題
次の問題はNPハードです
- 回路充足可能性の問題
- セットカバー
- 頂点カバー
- 巡回セールスマン問題
これに関連して、TSPがNP完全であることを説明します。
TSPはNP完全です
巡回セールスマン問題は、セールスマンと一連の都市で構成されています。 セールスマンは、特定の都市から始まり、同じ都市に戻る各都市を訪問する必要があります。 問題の課題は、巡回セールスマンが旅行の全長を最小限にしたいということです
証明
*_TSPがNP-Complete_* であることを証明するには、最初に *_TSPがNP_* に属していることを証明する必要があります。 TSPでは、ツアーを見つけ、ツアーに各頂点が1回含まれていることを確認します。 次に、ツアーのエッジの合計コストが計算されます。 最後に、コストが最小かどうかを確認します。 これは、多項式時間で完了することができます。 したがって、 *_ TSPはNP_* に属します。次に、 _ TSPがNP-hard_ であることを証明する必要があります。 これを証明する1つの方法は、 ハミルトニアンサイクル≤〜p〜TSP を示すことです（ハミルトニアンサイクルの問題はNPcompleteであることがわかっています）。
*_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 の各エッジのコストは、各エッジが E に属するため、 _ G ^ '^ ' の 0 であることは明らかです。 したがって、 ' G ^ '^ ' の _h' のコストは 0 です。 したがって、グラフ G のハミルトニアンサイクルがある場合、グラフ _G ^ '^ _ のコストは 0 になります。
逆に、 _ G ^ '^ ' のツアーのコストは最大で 0 の _h ^' ^ _ であると仮定します。 _E ^ '^ _ のエッジのコストは、定義により 0 および 1 です。 したがって、 ' h ^ '^ ' のコストは 0 であるため、各エッジのコストは 0 でなければなりません。 したがって、 ' h ^ '^ ' には _E' のエッジのみが含まれると結論付けます。
したがって、 _ G ^ '^ ' のコストツアーが最大で 0 である場合に限り、 ' G_ がハミルトニアンサイクルを持つことを証明しました。 TSPはNP完全です。
