日経サイエンス  2012年12月号

特集:「限界」を科学する

P対NP問題と知の限界

J. パブルス(サイエンスライター)

 答えを見つけるのは難しいかもしれないが答えがあっているかどうかは素早くチェックできる問題(ジグソーパズルのような問題)のことを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)

サイト内の関連記事を読む

キーワードをGoogleで検索する

P対NP問題P≠NP予想ゲーデル巡回セールスマン問題最小シュタイナー木問題