タイトルコード |
1000100152399 |
書誌種別 |
図書 |
書名 |
今度こそわかるP≠NP予想 |
書名ヨミ |
コンド コソ ワカル ピー エヌピー ヨソウ |
叢書名 |
今度こそわかるシリーズ
|
言語区分 |
日本語 |
著者名 |
渡辺 治/著
|
著者名ヨミ |
ワタナベ オサム |
出版地 |
東京 |
出版者 |
講談社
|
出版年月 |
2014.3 |
本体価格 |
¥2800 |
ISBN |
978-4-06-156600-2 |
ISBN |
4-06-156600-2 |
数量 |
8,177p |
大きさ |
21cm |
分類記号 |
410.9
|
件名 |
計算量理論
|
注記 |
文献:p171〜172 |
内容紹介 |
21世紀の数理科学の7大難関問題の「P≠NP予想」とはどんな予想なのか? P≠NP予想の概観から計算複雑さの基本、2013年時点での計算複雑さの理論の研究の最前線までを解説する。 |
著者紹介 |
東京工業大学理工学研究科情報科学専攻修士課程修了。同大学大学院情報理工学研究科教授・工学博士。著書に「計算可能性・計算の複雑さ入門」など。 |
目次タイトル |
第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 回路計算量における下界証明の最前線 |