ハミルトン閉路とNP

質問

ハミルトン閉路問題はNPに属する、という事を証明したいのですが…
これって　HCがPに属することを証明すれば良いのでしょうか？
ちょっと迷走しちゃってます…

回答No.2

Tacosan

ハミルトン閉路問題が P に属することを証明できたら, 大変なことになりますよ....
「ハミルトン閉路を持つグラフ」が本当に「ハミルトン閉路を持つ」ことを, あなたならどのように示しますか?

回答No.1

Tacosan

「HCがPに属することを証明すれば良いのでしょうか」というときの「HC」って何を指してますか?
「ある問題が NP に属する」ことを証明するには, 普通は「正例に対する証拠により多項式時間で検証できる」という方針を使うんじゃないかな. 「NP完全問題に帰着できる」ことを言ってもいいはずだけどなんか違和感があります.

お礼

すいません。HCっていうのはハミルトン閉路問題のことです。
帰着出来る事が証明出来ないのです…