「P≠NP」問題 現代数学の超難問 (ブルーバックス)

著者 : 野崎昭弘

• 講談社 (2015年9月18日発売)

作品紹介・あらすじ

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

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

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

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

感想・レビュー・書評

[おぬまさんの感想 · 2022年12月21日]

長らく積読としていた新書。タイトルから読まなければと思い買った記憶。
タイトル通り、P≠NP問題を解説してくれる新書で、そのためにコンピュータとは何か、といった前提から入ってくる。私はその構成が読みやすく、入り込みやすいと感じたが、他の人の感想を見ると評判が悪いようだ。
また、本題に入るあたりも、「急に話題が変わったように感じる」という意見が多い。私は大学でじっくりコンピュータサイエンスを学んでいるからか、何も違和感は感じなかった。逆に大学レベルの学問を一般に伝えるのは難しいのだと感じることができた。

個人的には復習も兼ねて、非常に理解できたが…

[ざき★やまさんの感想 · 2020年8月30日]

P≠ＮＰとはなんぞやと思って読んだけど、最初で躓いてしまった。数学を一からやり直さないと・・・

[ヤマスカさんの感想 · 2018年10月23日]

リーマン予想についてのブルーバックを読んだので、勢いで前から気になっていたP≠NP予想についてwikipediaよりも詳しく、と言う事で。

計算機の基礎からアルゴリズムを掠って本題へ。
脇道にそれて各種の蘊蓄を撒くタイプの本は好きだけれど、著者の愚痴とかだとちょっと残念。
「良くある誤解」部分はもうちょっと評価されても良かったのでは、と言うかそういう部分のウェイトが高いともっと理解が進むのかも知れない。

しかし、なぜ最新の研究者じゃないのだろう……。

[よはんさんの感想 · 2018年8月4日]

PとNPがどういう類の問題なのかがよくわかった。ページ数も少なめなので気楽に読める。ただし、まったく前提知識のない人が読んでも理解できないだろうとは思う。

[kemtarouさんの感想 · 2018年5月11日]

前半が本題とは直接関係のない初歩的知識の説明に費やされ、イライラ感が募る頃、ようやく本題に入るが解説がいきなりぶっ飛んだ内容で理解しにくい。チューリングマシンが登場して具体例で理解させようとする試みはまだるこく、もっと問題の本質での難しさについて紐解く解説が欲しかった。期待感とは裏腹の消化不良を感じさせる後味が残念である。

[ijklmnさんの感想 · 2017年11月30日]

易しそうで難しい、序盤簡単なので余計に難しく感じる

[yama219さんの感想 · 2017年4月1日]

P≠NP予想についての本なわけであるが、110ページ目までは本のタイトルと関係のない著者のうんちくが続くので読んでいて嫌になる。1回読んだだけではこの著者は何が言いたかったのか分から中なったのだが、ネットでP≠NP予想について調べたあと、110ページから解説される計算量理論から読み始めると、1回目に読んだ時とは違いアルゴリズム理論の考え方など、P≠NP予想を理解する上で必要な知識が解説されていることがわかった。もう一回ぐらい110ページ目から読みなおしてふんわりと掴んだ上で、他の本も読んでみたいと思った。

[taamoriさんの感想 · 2016年12月11日]

筆者はあの「ゲーデル・エッシャー・バッハ」の訳者。アキレスと亀の会話などアクロバチックな訳はいまだに語り草でるが、もともとはこうした未解決の数学問題に取り組む人である。本書は啓蒙書として優れているがどこか特定の人を批判する意図が随所にみられて読んでいてちょっと不快にさせる。わかる人にはわかるので堂々と書いて構わないのに、と思う。でも、かねてからの疑問が一つ氷解したので＋★。

[講談社ブルーバックスさんの感想 · 2015年12月25日]

ある問題が多項式時間(Ｐ)で解けるとは、そして非決定性多項式時間(ＮＰ)で解けるとはどういうことか。ミレニアム問題「Ｐ≠ＮＰ」に迫ります。

[たいちさんの感想 · 2015年12月14日]

いまいち理解ができませんでした。
人にこういった内容ですよと説明できるくらいにはなりたいのですが・・・

著者プロフィール

野崎昭弘

一九三六年（昭和一一年）、神奈川県生まれ。五九年、東京大学理学部数学科卒業。六一年、東京大学大学院修士課程修了。東京大学助手、山梨大学教授（計算機械学科）、国際基督教大学教授（理学科）、大妻女子大学教授（社会情報学部）、サイバー大学ＩＴ総合学部教授を歴任。現在，大妻女子大学名誉教授。専攻、情報数学。著書に『電子計算機と数学』（ダイヤモンド社）、『πの話』（岩波書店）、『とらんぷ』（ダイヤモンド社）、『計算数学セミナー』（日本評論社）、『詭弁論理学』『逆接論理学』（中公新書）、『計算機数学』（共立出版）、『数学的センス』（日本評論社）、『トランプひとり遊び』（朝日新聞社）、『はじまりの数学』（ちくまプリマー新書）ほか。

「2021年 『まるさんかく論理学』 で使われていた紹介文から引用しています。」