情報処理における全国のエキスパートが一堂に会したリクルート主催の「春の情報処理祭」。20世紀末のミレニアム懸賞にも選ばれた「P≠NP」という未解決問題に対して、アルゴリズムを用いたアプローチ方法を電気通信大学准教授の岡本吉央氏が解説しました。 P≠NP問題、進捗どうですか? 岡本吉央氏:よろしくお願いします。電気通信大学の岡本です。アルゴリズム分野の話をしたいんですが、なぜかP≠NP問題の話を今日はしようと思います。「みなさん、進捗どうですか?」というのがこの祭りのテーマなので、「P≠NP問題、進捗どうですか?」ということを話したいんですが、このP≠NP問題というのは、すごく大きな未解決問題なんです。 いろんなところで、これは未解決だと言われているんですけれども、これが今どのぐらい解決に向かって進んでいるのかということをお話ししたいと思います。私自身は計算幾何学とかグラスアルゴリズムとか、
![解けたら賞金1億円! 数学の7つの未解決問題のひとつ「P≠NP」問題へのアプローチがもたらすもの](https://cdn-ak-scissors.b.st-hatena.com/image/square/f93cf264bc6441f57e4497a6817e8d75b238051a/height=288;version=1;width=512/https%3A%2F%2Fimg.logmi.jp%2Fwp-content%2Fuploads%2F2015%2F03%2Fai11.jpg)