出産前後の痔にはご注意!

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

このQ&Aに関連する最新のQ&A

A 回答 (2件)

ハミルトン閉路問題が P に属することを証明できたら, 大変なことになりますよ....


「ハミルトン閉路を持つグラフ」が本当に「ハミルトン閉路を持つ」ことを, あなたならどのように示しますか?
    • good
    • 0

「HCがPに属することを証明すれば良いのでしょうか」というときの「HC」って何を指してますか?


「ある問題が NP に属する」ことを証明するには, 普通は「正例に対する証拠により多項式時間で検証できる」という方針を使うんじゃないかな. 「NP完全問題に帰着できる」ことを言ってもいいはずだけどなんか違和感があります.
    • good
    • 0
この回答へのお礼

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

お礼日時:2008/07/13 15:19

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング