ブルーバックス 「Ｐ≠ＮＰ」問題―現代数学の超難問

野崎 昭弘【著】

講談社（2015/09発売）

• サイズ 新書判／ページ数 224p／高さ 18cm
• 商品コード 9784062579339
• NDC分類 410.9
• Cコード C0241

出版社内容情報

コンピュータの歴史、アルゴリズムの理論の解説を経て、未解決であるミレニアム問題のひとつ、「Ｐ≠ＮＰ問題」に迫ります！現代社会において、あらゆるところに利用され、なくてはならない存在のコンピュータ。遥か昔、計算をするためだけの道具だった計算機は、歴史とともに発展し、現代のコンピュータの姿となったが、いまでももの凄いスピードで進化し続けている。

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

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

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

第0章　現代社会とコンピュータ
第1章　コンピュータとは何ものか
　1-1　人間から歯車式コンピュータまで
　1-2　現代の電子式コンピュータ
　1-3　現代の電卓・コンピュータの使い方
第2章　コンピュータ科学の誕生
　2-1　黎明期_計算可能性理論
　2-2　ハードウエアの設計理論
第3章　アルゴリズムの理論
　3-1　アルゴリズム理論の誕生
　3-2　アルゴリズム理論の展開_計算量理論
　3-3　アルゴリズム理論の題材
　3-4　アルゴリズム理論の成果
第4章　Ｐ≠ＮＰ問題
　4-1　“ＮＰ”の登場
　4-2　Ｐ≠ＮＰ問題
第5章　おわりに
　5-1　歴史を少々
　5-2　Ｐ≠ＮＰ問題のむずかしさ
　5-3　Ｐ≠ＮＰ問題を巡る、さまざまな展開
　5-4　Ｐ≠ＮＰ問題の重要性


野崎 昭弘［ノザキ アキヒロ］
著・文・その他

内容説明

問題を解く鍵はアルゴリズムと時間計算量だ！２０世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた多項式時間（Ｐ）で解けるとは、そして、非決定性多項式時間（ＮＰ）で解けるとはどういうことか。

目次

第０章　現代社会とコンピュータ
第１章　コンピュータとは何ものか
第２章　コンピュータ科学の誕生
第３章　アルゴリズムの理論
第４章　Ｐ≠ＮＰ問題
第５章　おわりに

著者等紹介

野崎昭弘［ノザキアキヒロ］
１９３６年、横浜市生まれ。東京大学理学部数学科卒業、同大学院数物系研究科修了。電電公社（現ＮＴＴ）電気通信研究所、東京大学教養学部、同理学部、山梨大学工学部、国際基督教大学教養学部、大妻女子大学社会情報学部、サイバー大学ＩＴ総合学部教授を経て、大妻女子大学名誉教授。専門はアルゴリズム理論、多値論理学、数学教育。『ゲーデル、エッシャー、バッハ』（共訳・白揚社、第２２回日本翻訳文化賞受賞）など、著書・和訳多数。第３回日本数学会出版賞受賞（本データはこの書籍が刊行された当時に掲載されていたものです）
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。

感想・レビュー

※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。

[ちくわん]

コンピューターは詳しいので、高速読み。ハルトマニスの「全員攻撃」発言が、この問題の難しさをあらわす。私の予想では、近いうちにインド関連が解決するだろう。さて、野崎先生が、本書を書くきっかけになった「一般向けの、実にひどい解説書」を探してみるか。

2018/10/13

[Satoshi]

PNP問題についての解説書かと思えば、前半は計算機科学の説明に費やされており、少し期待外れ。NPについて、少し解った気になれた。

2020/02/09

[とりもり]

他の暗号本で「P≠NP」問題に興味を持って読んでみたが、あまり良い本とは言えなかった。先ず、前半部分が冗長過ぎて、肝心の「P≠NP」問題の解説が詳しいとは言えない。正直、半分程度は著者の趣味の記述で、本題の理解には不要という気がする。それなら、本題の解説をもっと充実させて欲しかったというのが、偽らざる感想。この問題には関心があるが、がっつりロジックを追って理解するほどの時間はないので、もう少し手頃な本はないかな〜と思う。★★☆☆☆

2016/01/21

[トルネードＧ＆Ｔ]

アルゴリズム（プログラミング）における計算速度の目安となる「計算量」がどの程度であるのか、という学問領域における「まあまあ早く問題」と「そこそこ早く解ける問題」の差を求めようとする話。本文内で難易度わけがされており初心者は難しい部分を読み飛ばしてざっくりと内容を理解でき、上級者はある程度踏み込んだところまで理解を深められるような構造になっている。肝心の「P≠NP」の話は前書きで筆者も宣言しているようにほんの一部で大部分はそこに至るまでの前提知識の紹介となっているためざっくりとアルゴリズムについても学べる。

2016/03/06

[まえぞう]

有名な問題のひとつで、何のことかわからなかった話の概要が何となく理解できました。コンピューターサイエンスでは重要な話しなんでしょうが、説明は抽象的でついていくのが大変です。

2016/01/09