謎犬の耳

「量子コンピュータとは何か」ジョージ・ジョンソン（水谷　淳訳）（早川書房）

そろそろ佳境です。この本の最終章「宇宙一の難問」について。

P203　セールスマン巡回問題は「NP完全」すなわち「非決定論的に多項式時間で」解ける。つまり非決定論的コンピュータというものがあって、そいつは問題を解く各ステップでどの筋道を選ぶかランダムに決めるのだけれど、１００％幸運な万能機械であり、その偶然に選んだ筋道が常に正しい選択肢になっている。この場合は「多項式時間」で解けるわけだ。しかし普通のコンピュータ（量子コンピュータも）は決定論的なのでこの問題の解決には「指数関数的時間」がかかる。

P206　「充足化問題」も「NP完全」。出席者全員を満足させるパーティーの組み方はやはり人数に対して指数関数的に難しさが増大する。

P208　「NP=P」を証明できるか？もしそれができれば、「ある定理を証明するのは（証明が存在するとして）、それをチェックするのと同じくらい簡単なことになる」。フェルマーの最終定理は解くのに３５０年もかかったが、それが正しいかどうかチェックするのには数ヶ月しかかからなかった。NP=Pならば芸術作品の「創作は鑑定と同じくらい簡単なものになる」という比喩も面白い（新たなモーツァルトを生み出すこと）。