本書「今度こそわかる P ≠ NP」の概要のページです
本書の概要
世の中には言われてみれば「ああ，そうだね」と，すぐに合点が行くことが結構多い． 幾何の証明の補助線，新商品のアイデア，あるいは学問上の発見，等々， いわゆる，コロンブスのたまご的なことは， 日常から高度な学問分野まで，いろいろなところに顔を出す． 言われれば「なるほど！」と思うような発見である． この種の発見の重要性を コンピュータと数学の言葉で言い表したのが「P ≠ NP 予想」である．
世の中のコロンブスのたまご的発見問題すべてに対し， 高速で実用的なソフトウェアが作り出せれば素晴らしい． しかしながら，世の中はそんなに甘くはなさそうだ， というのが「P ≠ NP 予想」なのである．
そんなの当たり前，と思われるかもしれない． しかし， コンピュータの出現当初より，多くの研究者が挑戦してきて， 未だに解決の道筋すらわからないのである． 実際，21 世紀の 7 大数学難題とも言われている． 本書は， この「P ≠ NP 予想」を議論する上で基礎となる 「計算複雑さの理論」の入門書である．
もう少し詳しくは：
本書の「はじめに」
からの抜粋をご覧ください．
P ≠ NP 予想については：
渡辺の解説ページ「P ≠ NP 予想って何？」
もご覧ください．
本書の読み方： 「読書ガイド」
のページを参考にしてください．
詰まったときの「お助け」も順次追加していく予定です．
本書の目次
第１章 P ≠ NP 予想とは？
第２章 「計算」を議論するために
2.1 「計算問題」とは
2.2 アルゴリズム→原始計算機
2.3 アルゴリズム→組合せ論理回路
2.4 乱択アルゴリズム，乱択計算機
第３章 計算量クラス
3.1 計算量
3.2 クラス P, PSIZE
3.3 クラス NP
3.4 クラス BPP, RP, ZPP
3.5 組合せによる計算量クラス
第４章 計算複雑さ解析法＃１ 対角線論法
4.1 対角線論法の考え方
4.2 TIME[ell^2] ⊂ TIME[ell^5] の証明
4.3 時間階層定理
第５章 計算複雑さ解析法＃２ 還元
5.1 還元の考え方
5.2 多項式時間還元
5.3 NP-完全性
第６章 計算複雑さ解析法＃３ 模倣
6.1 NP ⊆ EXP の証明
6.2 クラス PH
6.3 BPP ⊆ PSIZE ならびに BPP ⊆ PH の証明
第７章 P ≠ NP 予想，最前線
7.1 計算量クラスの新たな特徴付け
7.2 脱乱化の最前線
7.3 回路計算量における下界証明の最前線
参考文献