「P≠NP」問題 現代数学の超難問 ブルーバックス

野崎昭弘(著者)

• 販売会社／発売会社: 講談社
• 発売年月日: 2015/09/19
• JAN: 9784062579339

商品レビュー

2026/01/26

P(多項式時間で解ける問題の集合)に対して、NP(Yesとなる証拠が与えられた問題に対して、多項式時間で検証できる問題の集合)の集合の方が大きいはずである、という予想についての解説。P≠NPである(と思われる)ことで、NPだがPではないというスキマで、暗号などのアルゴリズムがありうるのだが、P＝NPだとすると、NPなものはすべて多項式時間で解けることになってしまう。仮にこれが証明されたら、ビットコインの暴落などがまた起きるかもしれない。

2022/12/21

長らく積読としていた新書。タイトルから読まなければと思い買った記憶。
タイトル通り、P≠NP問題を解説してくれる新書で、そのためにコンピュータとは何か、といった前提から入ってくる。私はその構成が読みやすく、入り込みやすいと感じたが、他の人の感想を見ると評判が悪いようだ。
また、本題に入るあたりも、「急に話題が変わったように感じる」という意見が多い。私は大学でじっくりコンピュータサイエンスを学んでいるからか、何も違和感は感じなかった。逆に大学レベルの学問を一般に伝えるのは難しいのだと感じることができた。

個人的には復習も兼ねて、非常に理解できたが…

2018/10/23

リーマン予想についてのブルーバックを読んだので、勢いで前から気になっていたP≠NP予想についてwikipediaよりも詳しく、と言う事で。

計算機の基礎からアルゴリズムを掠って本題へ。
脇道にそれて各種の蘊蓄を撒くタイプの本は好きだけれど、著者の愚痴とかだとちょっと残念。
「良くある誤解」部分はもうちょっと評価されても良かったのでは、と言うかそういう部分のウェイトが高いともっと理解が進むのかも知れない。

しかし、なぜ最新の研究者じゃないのだろう……。