P対NP問題と知の限界

　答えを見つけるのは難しいかもしれないが答えがあっているかどうかは素早くチェックできる問題（ジグソーパズルのような問題）のことをNP問題，簡単に素早く解ける問題のことをP問題という。「素早く解けるP問題はすべて，答えを素早く確認できるNP問題である」ことが証明されているが，その逆はどうだろうか。つまり「答えを素早く確認できるNP問題はすべて，素早く解けるか？」──これが「P対NP問題」だ。

　直観的には両者は異なると思われ，多くの数学者もP≠NPだと信じてはいるが，まだ誰も証明できていない。もし両者に本質的な差がないとすると，コンピューターはすべてのP問題を効率的に解けるので，NP問題も同様に解けることになり，コンピューターで計算できる限界が一挙に広がる。

　逆にP≠NPであれば，コンピューターにできることはもちろん，知りうることに基本的な限界があることになる。知りうる知識に限界が課せられているのは，この宇宙の最も基本的なところに組み込まれた原理なのかもしれない。