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

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

• 要旨（「BOOK」データベースより）

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

• 目次

  第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　Ｐ≠ＮＰ問題の重要性

• 出版社からのコメント

  コンピュータの歴史、アルゴリズムの理論の解説を経て、未解決であるミレニアム問題のひとつ、「Ｐ≠ＮＰ問題」に迫ります！

• 内容紹介

  20世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた「多項式時間（P）で解ける」とは。そして、「非決定性多項式時間（NP）で解ける」とはどういうことか。ミレニアム問題の１つ、現在でも未解決の数学の難問を、コンピュータの歴史からさかのぼって説明します。
  
  
  現代社会において、あらゆるところに利用され、なくてはならない存在のコンピュータ。遥か昔、計算をするためだけの道具だった計算機は、歴史とともに発展し、現代のコンピュータの姿となったが、いまでももの凄いスピードで進化し続けている。
  
  このコンピュータの発展とともに生まれたのが、計算の方法・手順を考えるアルゴリズムの理論や、そして計算量の理論だ。計算の複雑さからアルゴリズムの評価が検討され、問題を解く上での基本ステップの実行回数から時間計算量が考えられてきた。
  ある問題のアルゴリズムが作れたからといって、その問題がきれいに簡単に解けるのだろうか？　－－答えはＮＯだ。問題を解くアルゴリズムを作れたからといって、実際にコンピュータに計算させたら、果てしない時間（例えば地球の寿命を超えるような時間）がかかってしまうような問題もある。
  
  「問題が解ける・解けない」「計算できる・計算できない」を考えたとき、問題の難易度によって、クラスＰの問題とかクラスＮＰの問題とかにクラス分けができる。このクラスＰとクラスＮＰが完全に一致するかどうかを決めるのが、Ｐ≠ＮＰ問題である。1971年以来、多くの数学者が挑戦し続けているが、Ｐ≠ＮＰ（ＰとＮＰが一致しない）であるか、Ｐ＝ＮＰ（ＰとＮＰが一致する）であるか、どちらも証明されていない。現代数学における未解決の超難問である。
  
  本書は、コンピュータの歴史から、アルゴリズム理論、計算量理論を経て、「Ｐ≠ＮＰ問題」を丁寧に解説し、2000年にアメリカのクレイ研究所がミレニアム問題として懸賞金を懸けた7つの難問の一つ、「Ｐ≠ＮＰ問題」に迫ります。

• 著者紹介（「BOOK著者紹介情報」より）（本データはこの書籍が刊行された当時に掲載されていたものです）

  野崎 昭弘(ノザキ アキヒロ)
  １９３６年、横浜市生まれ。東京大学理学部数学科卒業、同大学院数物系研究科修了。電電公社（現ＮＴＴ）電気通信研究所、東京大学教養学部、同理学部、山梨大学工学部、国際基督教大学教養学部、大妻女子大学社会情報学部、サイバー大学ＩＴ総合学部教授を経て、大妻女子大学名誉教授。専門はアルゴリズム理論、多値論理学、数学教育。『ゲーデル、エッシャー、バッハ』（共訳・白揚社、第２２回日本翻訳文化賞受賞）など、著書・和訳多数。第３回日本数学会出版賞受賞

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