数学特別演習（第13回）

今日は、計算の複雑さが話題の中心になりました。「決定問題」や「NP問題」、「NP困難」の概念、ハミルトン閉路を求める問題が「NP困難」な問題の一つである事実、等です。

ハミルトン閉路が「存在するか」を問う問題は「NP問題」であっても、逆にハミルトン閉路が「存在しないか」を問う問題が、いまだにわかっていない、というのは、ちょっと意外な気もしましたが、存在を証明するより非存在を証明する方が難しい、ということを考えると、なるほどと思います。

それから、このテキストの最小の方で出てきた「負の重さが許されるグラフにおいて、最大でも一度だけ通過が許される最短経路問題」を効率的に解くアルゴリズムがあるとしたら、そのアルゴリズムを用いてハミルトン閉路問題も効率的に解くことが可能である、という命題の証明を通して、あるNP困難な命題から別の問題がNP困難である事実を導くというやり方も扱いましたが、最初の命題の証明も、なかなかすぐにはピンとこない人もいたようです。

今回は、全体的にやや難しい内容でしたが、この辺から「巡回セールスマン問題」の話題に入っていくと思うので、がんばって予習／復習をしてほしいと思います。