今度こそわかるP≠NP予想

渡辺治・著
シリーズ:
今度こそわかるシリーズ

今度こそわかるP≠NP予想

発行
2014/03/20
サイズ
A5判
ページ数
185
ISBN
978-4-06-156600-2
本体
2800円(税別)
在庫
在庫あり

書籍を購入する

本体
2800円(税別)

電子書籍

※価格は紙の本と異なります。また、書店によって価格が異なる場合もあります。※配信開始日は各書店により異なります。書店によっては取り扱いのない作品もございます。あらかじめご了承ください。
電子書籍版を見る

内容紹介

初学者がつまずくところを熟知した著者による,丁寧な解説.
計算機科学の最重要難問に挑む!

◆計算機科学の独特の記法や言い回しをしっかりと説明し,
 初学者がスムーズに理解を進められるように工夫しました.
◆P≠NP予想の背後にある考え方を実感できるように,
 わかりやすい具体例と図表を,ふんだんに取り入れました.
◆近年の新しい発見も解説し,最先端の研究への架け橋となる一冊です.

〈本書第1章より〉
 多分,我々が予想するようにP≠NPであろう.けれども人類はそんな事実にへこたれない.P=NPの世界がそんなによいのであれば,それを人類が目指すだろうし,目指すべきなのである.ただし,P≠NP なので,すべてのNP問題を一気に解決するような特効薬は存在しないし,どのNP問題も完璧には解決できない.世の中,そんなに甘くはないのである.各々の問題ごとに,その問題個別の手法で,できる限り解くしか手はないのだ.
 こうした難しい挑戦に我々が挑む際,必須となるのが計算の難しさの本質の理解である.直面する計算の難しさを分析し,それを克服・回避する手法を導いてくれるような強力な数学分野である.P≠NPという不可能性の証明を目指すことで,こうした強力な数学分野を生み出すことが重要なのである.

目次

はじめに
本書の構成について

第1章 P≠NP予想とは?

第2章 「計算」を議論するために
 2.1 「計算問題」とは
 2.2 アルゴリズム → 原始計算機
 2.3 アルゴリズム → 組合せ論理回路
 2.4 乱択アルゴリズム,乱択計算機

第3章 計算量クラス
 3.1 計算量
 3.2 クラスP, PSIZE
 3.3 クラスNP
 3.4 クラスBPP, RP, ZPP
 3.5 組合せによる計算量クラス

第4章 計算複雑さ解析法#1 対角線論法
 4.1 対角線論法の考え方
 4.2 TIME[l^2] 〓 TIME[l^5] の証明
 4.3 時間階層定理

第5章 計算複雑さ解析法#2 還元
 5.1 還元の考え方
 5.2 多項式時間還元
 5.3 NP-完全性

第6章 計算複雑さ解析法#3 模倣
 6.1 NP ⊆ EXP の証明
 6.2 クラスPH
 6.3 BPP ⊆ PSIZE ならびにBPP ⊆ PH の証明

第7章 P≠NP予想,最前線
 7.1 計算量クラスの新たな特徴付け
 7.2 脱乱化の最前線
 7.3 回路計算量における下界証明の最前線

参考文献
索引