「Ｐ≠ＮＰ」問題　現代数学の超難問

投稿元：

レビューを見る

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

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

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

投稿元：

レビューを見る

PとNPがどういう類の問題なのかがよくわかった。ページ数も少なめなので気楽に読める。ただし、まったく前提知識のない人が読んでも理解できないだろうとは思う。

投稿元：

レビューを見る

いまいち理解ができませんでした。
人にこういった内容ですよと説明できるくらいにはなりたいのですが・・・

投稿元：

レビューを見る

野崎先生の本は分かりやすいからずいぶん期待して読み始めた。前半は良かった。が、後半タイトル通りの本題に入ったあたりから全くついていけなくなってしまった。私が理解したのは以下のようなこと。コンピュータにいろいろ問題を与えたとして、その解き方によっては、時間のかかり方がずいぶん違うのだということ。そして、その問題には有限の時間で解けるものとそうでないものがあるということ。それをきちんと証明するのはずいぶんと難しい問題であるということ。なんとなく、これくらいです。ただ、野崎先生が本書を書こうと思った動機がおもしろい。どうやら、同じテーマの「とんでも本」が出ているようだ。これはいかんと、執筆を始められたのだろう。ところで、２進法・１６進法の置き換えと、電卓による複利計算の方法は（最少の手順で２の１０乗を計算するなど）高校入試の問題にも使えそうでおもしろい。

投稿元：

レビューを見る

ある問題が多項式時間(Ｐ)で解けるとは、そして非決定性多項式時間(ＮＰ)で解けるとはどういうことか。ミレニアム問題「Ｐ≠ＮＰ」に迫ります。

投稿元：

レビューを見る

前半が本題とは直接関係のない初歩的知識の説明に費やされ、イライラ感が募る頃、ようやく本題に入るが解説がいきなりぶっ飛んだ内容で理解しにくい。チューリングマシンが登場して具体例で理解させようとする試みはまだるこく、もっと問題の本質での難しさについて紐解く解説が欲しかった。期待感とは裏腹の消化不良を感じさせる後味が残念である。

投稿元：

レビューを見る

筆者はあの「ゲーデル・エッシャー・バッハ」の訳者。アキレスと亀の会話などアクロバチックな訳はいまだに語り草でるが、もともとはこうした未解決の数学問題に取り組む人である。本書は啓蒙書として優れているがどこか特定の人を批判する意図が随所にみられて読んでいてちょっと不快にさせる。わかる人にはわかるので堂々と書いて構わないのに、と思う。でも、かねてからの疑問が一つ氷解したので＋★。