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

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

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

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

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

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

Comments

まだコメントはありません / No comment.

Send comment


Name


Mail-address (empty is OK. If you want to notify update, please fill mail-address.)


Bot check code (240329 と入力してください / Please input 240329.)