ハミルトニアンサイクルを削減して、グラフの色をグラフ化します

Question

3-SATの問題は、グラフの着色と監督されたハミルトニアンサイクルの問題の両方に減らすことができますが、指示されたハミルトニアンサイクルを多項式時間のグラフのグラフに減らす削減のチェーンはありますか？

Answer 1

$ q in sf {np} $ and $ q ' in sf {np text { - } hard} $とします。次に、定義上、$ Q $は（多くの）多項式時間で$ Q '$に削減できます。

削減の正確なチェーンは、$ sf {np text { - } hard} $ ness $ q '$の証明に依存します。通常、それは$ mathrm {sat} $から始まり、$ q '$で終わる一連の削減によって証明され、次に使用します クックレビン 定理。したがって、削減のチェーンは、$ q $から$ mathrm {sat} $に削減され、その後、$ mathrm {sat} $から$ q '$に削減されます。

通常、必要な特性を直接表現する命題式を簡単に見つけるのが簡単であるため、通常、特定の問題に対してより直接的な削減があります（Cook-levinを使用することはありません）。たとえば、指示されたHamiltionian Path（$ mathrm {dhp} $）およびグラフカラー（$ mathrm {gc} $）の場合、次のことを減らすことができます。

• $ mathrm {dhp} $ to $ mathrm {sat} $、
• $ mathrm {sat} $ to $ mathrm {3sat} $、
• $ mathrm {3sat} $ to $ mathrm {gc} $。