読者です 読者をやめる 読者になる 読者になる

ゲーデルの不完全性定理とP≠NP問題に想う

戯言 面白科学

「証明できない問題がある」ということを証明したゲーデル不完全性定理。簡単に言えば「無理なものは無理」ってことを証明したということだ。
当然ながら、僕は本定理がどのようにして証明されたのかは知らない。知らないが、「証明できると仮定すると矛盾が生じる」みたいなアプローチで証明されているのではないかと勝手に想像している。
ところで、P≠NPを証明した、とする論文が以前話題になった。実際は証明できてはいなかったようだが、その論文の広がり方がP≠NP問題に対する関心の大きさを物語っていると言えるだろう。
このP≠NP問題がどういった問題かをもの凄く簡単に言うと

時間をかければ解ける問題に、時間をかけなくても解く方法はあるか

ということで、P=NPなら「簡単な方法あるよ」、P≠NPなら「そんな簡単な方法はありません」ということになる。最近の研究者達のほとんどはP≠NPだと考えている。
そして、仮にP≠NPが証明された場合に一体何が起きるのかというと、実は特に何も起こらない。強いて言うなら、超効率的なアルゴリズムを考えるために無駄な努力をする必要がなくなるくらい。だって、NPに入ったら計算困難なんだもん。
じゃあ、P≠NPを証明することが無意味かというと、そんなことは無い。
ゲーデル不完全性定理を思い出してもらいたい。これは「証明できないものもある」ということを主張する。
そしてP≠NPが証明されることとはすなわち、「簡単には計算できないものもある」ということだ。
この二つが出揃うことで、有史以来、我々を悩ませ続けてきた、あの問題を解決することができるようになるのだ。

「ねぇ、私のこと好き?」
「好きだよ」
「本当に?」
「うん」
「じゃあ証明してよ」
「世の中にはゲーデル不完全性定理というものがあってだな」
「よく分かんないけど…じゃあ私のことどれくらい好き?」
「うーん、それはNP問題だから、直ぐには答えを導き出せn..」
「もういい」