じっくりと問題を考えてみる

システム制御という授業の課題.
ある問題がNP完全かどうかを多項式還元可能かどうかということから,証明する.
使って良い問題も限られていて,

・ハミルトン閉路
・ナップザック問題
・巡回セールスマン問題

の3つ.ちなみに答えがあるかどうかは,先生も知らない(笑)
うーん,直接導くのは難しそうだし,何か中間問題をひとつつくってやる必要がありそう.

こうやっていろいろと考えることは面白い.
ただ,こうやってやっていると,普段じっくりと問題を考えてないことがわかるなぁ orz

Posted at : 2011-06-24 19:30:29 / Category : none

コメント

まだコメントはありません

コメントを投稿


お名前


メールアドレス(返信を通知する場合のみ記入)


認証コード(210119 と記入してください)