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

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

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

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