「Ｐ≠ＮＰ」問題

20世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた「多項式時間（P）で解ける」とは。そして、「非決定性多項式時間（NP）で解ける」とはどういうことか。ミレニアム問題の１つ、現在でも未解決の数学の難問を、コンピュータの歴史からさかのぼって説明します。


現代社会において、あらゆるところに利用され、なくてはならない存在のコンピュータ。遥か昔、計算をするためだけの道具だった計算機は、歴史とともに発展し、現代のコンピュータの姿となったが、いまでももの凄いスピードで進化し続けている。

このコンピュータの発展とともに生まれたのが、計算の方法・手順を考えるアルゴリズムの理論や、そして計算量の理論だ。計算の複雑さからアルゴリズムの評価が検討され、問題を解く上での基本ステップの実行回数から時間計算量が考えられてきた。
ある問題のアルゴリズムが作れたからといって、その問題がきれいに簡単に解けるのだろうか？　－－答えはＮＯだ。問題を解くアルゴリズムを作れたからといって、実際にコンピュータに計算させたら、果てしない時間（例えば地球の寿命を超えるような時間）がかかってしまうような問題もある。

「問題が解ける・解けない」「計算できる・計算できない」を考えたとき、問題の難易度によって、クラスＰの問題とかクラスＮＰの問題とかにクラス分けができる。このクラスＰとクラスＮＰが完全に一致するかどうかを決めるのが、Ｐ≠ＮＰ問題である。1971年以来、多くの数学者が挑戦し続けているが、Ｐ≠ＮＰ（ＰとＮＰが一致しない）であるか、Ｐ＝ＮＰ（ＰとＮＰが一致する）であるか、どちらも証明されていない。現代数学における未解決の超難問である。

本書は、コンピュータの歴史から、アルゴリズム理論、計算量理論を経て、「Ｐ≠ＮＰ問題」を丁寧に解説し、2000年にアメリカのクレイ研究所がミレニアム問題として懸賞金を懸けた7つの難問の一つ、「Ｐ≠ＮＰ問題」に迫ります。