« 昔を知ってるから | メイン | まずはめでたいが »
2010年06月13日
「出来ないこと」を証明するのは難しい
「出来ること」を証明するには、うまくいく方法を１つ示せばいい。 しかし、「出来ないこと」を示すのは、それほど簡単ではない。 下手なやりかたで「出来ない」と云っても、「もっとうまい方法を探せば？」ということになる。 どんなやり方をしても出来ない、という必要がある。 難しい問題は、それが難しいのである。
計算の理論の世界では、問題を解くアルゴリズムに２つの計算時間のタイプがある。 P（決定的多項式時間）とNP（非決定的多項式時間）の２つであるが、長年の課題は「P≠NP問題」を証明するという問題である。 1970年代、計算の理論の研究者のうちの一部はこの証明に躍起だったし、現在でも未解決な難解問題の一つである。
計算の理論にも興味を持っていたが、マイクロプロセッサ誕生の時期でもあり、研究対象のメインはそれに移行していた。 日本にいるときは、「P≠NP問題」は他山の石だったが、外国での研究機会を得たときちょっと色気が出た。 フランスで実験装置を手配するのは面倒だし、理論なら業者に電話をかけたりする手間が要らなかった、という背景もあった。
この問題解決のため、朝から晩まで研究室内をクマみたいに歩き廻った。 「証明できた！」と思って書き始めたら、どうどうめぐりの論法になるのに気づいた。 つまり、ほかの研究者と同じ落とし穴に落ちたのである。 1週間これに没頭した結果であるが、あっさりあきらめて、別の問題解決に切り替えたが、少なくとも「自分は証明できない」ということを示すことはできた。
離散数学の講義で、TSP（巡回セールスマン問題）が出てきたので、ちょっとした思い出話を書いた次第。
投稿者 tadashi : 2010年06月13日 17:11