メモ

クレイ研究所のミレニアム賞（総額700万ドル）の7つの健勝問題の一つに「P vs NP 問題」がある。これは9世紀の数学者が提示した巡礼問題（NP）と同じ。巡礼路の計算をしらみつぶしに行なえば、計算時間は寺の数と指数関数となり非現実的となる。しらみつぶし法以外の方法は現在のところ知られていない。似ているが一筆書き問題（P）は現実的な計算時間で解決可能である。巡礼路問題も道順の候補がヒントとして与えられれば計算時間が現実的な時間に収まる。現在のところPはNPに含まれるが、同じではないと考えられている。

丸岡章教授　青葉工業会ニュース第39号