コンセプトの明確化が必要でした。問題が NP 完全であることを証明するために、リダクションを使用します。
ここで、L<=L' があるとします。L から L' への削減がありますか、それとも逆の方法で行うことはできますか? つまり、L が L' を使用して解決できる場合、L' は NP 完全であることを示すことができますか??
私はこれに関してかなり混乱しています。
例えば。ハム サイクルからハム パスへの削減については、逆方向にします。
また、「少なくとも k 個のエッジを持つグラフに s から t へのパスがあるかどうか」を示す必要があるという問題を、ハム サイクルからのリダクションで解決できません。
上記の問題について説明し、私を導いてください。ありがとう
言語LがNP完全であることを示すには、実際には2つのことを証明する必要があります。LはNPであり、LはNP困難です。通常、LがNPにあることを証明するのは簡単ですが、それを忘れないでください。
LがNP困難であることを示す通常の方法は、事実上、Lの多項式時間決定子を使用して、NP完全であることが証明されている言語L'の多項式時間決定子を構築できることを示すことです。
それはそのようでなければなりません。NP完全言語の多項式時間決定器から多項式時間決定器を構築できる多項式時間決定可能言語Lの場合が多くあります。たとえば、グラフを2色で着色する多項式時間決定可能問題と、NP完全一般グラフ彩色問題を考えてみます。
ハミルトン閉路についてのあなたの質問に対するコメントでヒントを与えました。ヒントを読んで考えたことはありますか？もしそうなら、その質問に答えてください。