■郵便配達夫は、N!度ベルを鳴らす

ついにやってしまった;;これまで、出来の悪い生徒ながら皆勤賞だけが唯一の取得だったのに、録画予約を失敗して受講できなかった「コマネチ大学数学科」。とくに今回の問題は「郵便配達問題」ということで楽しみにしていただけ残念だ。

「郵便配達問題」とは、郵便物を配達するのに最短のルートを求める問題だ。郵便局をスタート地点とすると、配達する家が5軒なら、その経路は、5!=120通り。10軒なら、10!=約360万通り……これが1000軒とか、1万軒となると、すべての経路を計算して答えを見つけるやり方では対処できなくなる。

現在のノイマン型コンピュータを使う限り、計算可能な問題(P)と、検算可能な問題(NP)は、等しくないと思われている。「P≠NP予想」は、ミレニアム懸賞問題のひとつで、賞金100万ドルが懸けられている。

量子コンピュータなどが作られ、もしも、この問題が「P=NP」であることが証明されたら、現在のRSA暗号などは、その安全性を確保できないことになっちゃう。

ということで、「コマネチ大学」の10分で解ける「郵便配達」問題とは、いかなるものだったのか……(orz)。