情報理工学院 数理・計算科学系 渡辺研究室

本書「今度こそわかる P ≠ NP」の読書ガイドのページです

読み方ガイド

全部で 7 章からなる本書の主要部分は第 2 章～第 6 章です． それに対し，第 1 章は「P ≠ NP 予想」の概観． この章を読むだけでも 「P ≠ NP 予想」が，ひと通りわかるでしょう． それに続いて，計算複雑 さの基本を第 2 章～第 6 章で説明していきます． 一方，第 7 章では，現在の（本書を書いた 2014 年時点での） 計算複雑さの理論の研究の最前線を紹介しました．

第 1 章から順に読んで頂くのが順当な読み方ですが， 第 1 章の後， 一気に第 7 章をながめてみるという手もあります． もちろん，用語や記号など，さっぱりわからないかもしれませんが， 最先端の研究の雰囲気が何となく感じられると思います． その後で第 2 章に戻って基礎から諸概念を理解していく，のもよいでしょう．

第 2 章の計算モデルの説明や第 3 章の計算量の考え方は， ちょっとした難関です． 正確な議論のためには，細かなところも避けられません． でも，どこかでつまづいても， 少し先まで読み進んでしまうことをお勧めします． 後で見返してみると，こういうことか！とわかる場合もありますから．

なお，著者の大学（東京工業大学）の大学院の計算量理論の授業では， 第 2 章～第 6 章の大部分を，半年間の講義で教えています． 最後のいくつかの話題は省略しています．

本書では， 実感をつかんで頂くために「実感しよう」というコーナーを設けました． つまづいたら，ここに理解へのヒントがあるかもしれません． 一方，細かなことが気になる，という方のために， 「こだわり」のコーナーも作りました． このコーナーは最初は読み飛ばして頂いても構いません．

お助け補足説明

※以降，記述を短くするため「デスマス調」から「デアル調」に変える．

どの分野もそうだが，その分野の基本的な用語や記号， あるいは説明方法に不慣れな最初のうちは， 教科書などを読んでも行き詰まることが多い． 計算複雑さの理論も同様だ．
と言っても，あまり丁寧に書いていては，ページ数が増えるばかり． そこで，少し丁寧な説明が必要な個所， とくに読者が「うっ」と詰まりそうなところを， このウェブページで補足することにした． まあ，一機にいろいろできないので，少しずつ書き足して行く計画である． （ここがわからない！ご指摘があれば， そこを「できるだけ」優先して書きますのでご用命ください．）

第 2 章のポイントとつまづき所

第 2 章では，計算問題とは，計算モデル（＝計算を表わす方法）とは，について 説明している．このうち，計算モデル（原始計算機械，組合せ論理回路）には， つまづき所が多数ある．これらを回避する方法を紹介しよう．

実は，計算モデル（とくに原始計算機械）の説明は，適当に読み飛ばしてもよい． 後の定理をきっちり書くためには，どうしても必要なので説明しなければならない． 著者としても悩ましかったところだったのだ．

なぜ，読み飛ばしてよいのか？ プログラムを書いた経験がある人ならば，「計算」（＝コンピュータによる処理） は，基本的な命令ステップを組合わせることで構成できる，ということは よくわかっているだろう．そういう人にとっては， 自分なりの「基本ステップ」の基準を使って， 計算時間＝基本ステップ数 と定義しても構わない．その理解で第 3 章，第 4 章に進んでも構わないのだ． （回路や乱択計算については見ておく必要はある．これについては後で述べる．）

こうした読み方で問題が生じるのは，具体的には定理 2.1 や定理 4.1 であり， ほぼそれらのみである．これらは，通常の計算を回路やインタープリタで 模倣（シミュレーション）するときの計算コストの見積もりに関する定理だ． これらをキッチリ説明したいががめに，原始計算機械のような計算モデルが 必要であり，細かな定義が必要だったのだ．だから，これらを「私は信じる！」 と腹をくくれば（？）飛ばし読みも可能である．

ただし，プログラミングの経験が無い人や浅い人には，この機会に「計算」とは 何かを知ってもらった方がよい．以下の補足説明などを参考に， ある程度は理解してもらいたい．

プログラミングが得意な人でも，回路や乱択計算には馴染みがない人も多いだろう． 回路も定理 2.1 を信じれば，ここは読み飛ばしても構わない．けれども，回路の 独特な点は 2 点だけ（非一様性と並列性）なので，そう難しいことではない． 以下の補足説明も参考にして欲しい．一方，乱択計算は今後，世の中で多く 使われるようになってくると思うので，この機会に感覚をつかんでおこう．

原始計算機械と原始プログラム

原始計算機械は本書特有の計算モデルだ．ただし， 一般に RAM (Random Access Machine) モデルと呼ばれているものと本質的 には同じである．この原始計算機械（ならびに原始プログラム）に戸惑いを持っ た人も多いだろう．ただし，二つの異なったタイプの戸惑いがある （と想像する）．

それぞれの戸惑いに対する補足を以下に用意した．

組合せ論理回路（本書では，単に「回路」と呼ぶ）

回路と言っても計算複雑さの理論で， 計算モデルとして登場する組合せ論理回路は繰り返しの無い， 下（入力）から上（出力）まで順次計算を進める単純なものだ． それが独特なので（実際の電子回路と大きく違うので） 違和感を持つ人もいるかもしれない． ただ，その点と，もう 1 つ回路の非一様性のみが， 回路計算モデルの独特な点である． この 2 点について 回路計算の補足で少し詳しく説明する．

第 3 章のポイントとつまづき所

この章では各種計算量クラスを定義している． そこでポイントとなるのは「計算量」という概念， そして，本丸の NP という計算量クラスだろう． なお「計算量クラス」とは， ある基準（その基準には様々な種類があるが） で計算問題を分類して得られる計算問題の集合のことである．

計算量と， そのオーダー記法による表わし方は， 最初はちょっと近寄り難いかもしれない． しかし， 計算量は関数である（つまり，1 つの数ではない）， 関数の大小比較には漸近的な比較を用いる， という 2 点さえ常に気を付けて読んでいけば，次第に慣れてくると思う． （もし，「ここがわからん！」という点があったらご指摘ください． 説明を追加しますので．）

一方，NP 問題の定義自体は，そう難しくはない（と思う）． 1 つ注意すべき点は， NP 問題（決定問題）では， Yes の意味と No の意味が大きく異なる点である． 「証拠の有る無し」が Yes, No の差なので， 対称的に感じられるが， 証拠が有る状況と無い状況は計算の立場から見ると大分異なるのである．

第 4 章のポイントとつまづき所

ここまで来れたのであれば，もう大丈夫！！ だと思うのだが．．．