NP 問題を使用したリダクションを理解するのに苦労しており、明確にしたいと思います。次の問題を検討してください。
Show that the following problem is NP-Complete by designing
a polynomial-time reduction algorithm from an already known
NP-Complete problem.
Problem: Given an undirected graph G=(V,E) and integer k,
test whether G has a cycle of length k.
この件に関しては他にも話題があることは知っていますが、このような削減がどのように行われるかはまだわかりません.
これが、このような問題にアプローチする方法であることを理解しています。
- 与えられた問題が多項式時間で解けると仮定します。
- 与えられた問題を使用して、多項式時間で NP 困難であることがわかっている問題を解きます
- これは矛盾を生み出すので、仮定は間違っているに違いない
- したがって、与えられた問題は多項式時間で解けてはなりません
では、このような問題の場合、これは適切なアプローチでしょうか?
- グラフのハミルトニアン サイクルの長さとして k を選択した場合 (ハミルトン サイクルがあると仮定)、この問題を使用してグラフのハミルトン サイクルを見つけることができます。
- ハミルトニアン サイクルは NP 時間でしか見つからないため、この問題も NP 時間でしか解けないはずです。