
答えを見つけるのは難しいかもしれないが答えがあっているかどうかは素早くチェックできる問題(ジグソーパズルのような問題)のことをNP問題,簡単に素早く解ける問題のことをP問題という。「素早く解けるP問題はすべて,答えを素早く確認できるNP問題である」ことが証明されているが,その逆はどうだろうか。つまり「答えを素早く確認できるNP問題はすべて,素早く解けるか?」──これが「P対NP問題」だ。
直観的には両者は異なると思われ,多くの数学者もP≠NPだと信じてはいるが,まだ誰も証明できていない。もし両者に本質的な差がないとすると,コンピューターはすべてのP問題を効率的に解けるので,NP問題も同様に解けることになり,コンピューターで計算できる限界が一挙に広がる。
逆にP≠NPであれば,コンピューターにできることはもちろん,知りうることに基本的な限界があることになる。知りうる知識に限界が課せられているのは,この宇宙の最も基本的なところに組み込まれた原理なのかもしれない。
著者
John Pavlus
科学,技術,デザインを専門とするライター・映画制作者。Wired誌,Nature誌,Technology Review誌などに執筆している。
原題名
Machines of the Infinite(SCIENTIFIC AMERICAN September 2012)
サイト内の関連記事を読む
P対NP問題/RSA暗号/ゲーデルの不完全性定理/巡回セールスマン問題/数学/計算複雑性/量子コンピューター
キーワードをGoogleで検索する
P対NP問題/P≠NP予想/ゲーデル/巡回セールスマン問題/最小シュタイナー木問題