現代数学の超難問
「Ｐ≠ＮＰ」問題とはなんだろう

野﨑昭弘＝著『「Ｐ≠ＮＰ」問題　現代数学の超難問』

ブルーバックス前書き図書館

upperline

〔photo〕iStock

問題を解く鍵はアルゴリズムと時間計算量だ!

20世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた多項式時間（P）で解けるとは。そして、非決定性多項式時間（NP）で解けるとはどういうことか。100万ドルが懸ったミレニアム問題、未解決の「P≠NP」問題に迫ります！

まえがき

私は東京大学理学部数学科で修士課程まで、純粋数学を勉強してから、電電公社（現ＮＴＴ）の研究所に就職し、情報科学に転向した。その後、東大教養学部に戻った頃から、アルゴリズムの理論（計算量の理論、第3章で解説する）が急速に拡がり、発展途上の分野の研究に参加できたのは、ありがたいことであった。

しかし私はどちらかというと、たとえば「データを小さい順に並べ替える」というような「実用性がある、理論的にはやさしい問題」に興味があったので、Ｐ≠ＮＰ問題のようにむずかしい問題にはあまり関心がなかった。それが1990年に京都で開かれた国際数学者会議で、ロシアの若い数学者ラズボロフがＰ≠ＮＰ問題でネヴァンリンナ賞を受賞した関係で、あわてて少し勉強するはめになった。

ずっと後に、講談社の小澤久さんから「ブルーバックスで、Ｐ≠ＮＰの解説を書かないか」とお誘いを受けた。この問題については一般向けのよい解説書がなかったので、うっかり引き受けてしまったが、なかなか書き始める気力がわかず、ずるずると引き延ばしていた。しかし昨年「一般向けの、実にひどい解説書」が出たために、急に元気が出て書き始め、何とかまとめることができた。

本書の核心部分は、第4章前半に「ＮＰの概念のポイント」として挙げた「3つのインチキ」で、雑誌『科学』（岩波、2007年10月号）で書いたことであるが、今でもわかりやすい説明ではないかと思う。また第5章第3節も、前記「実にひどい解説書」による誤解を予防・解毒するために力を入れて書いたのであるが、最初は原著者の意図も取り入れようとして、私まで毒に染まって、不正確な書き方になっていた。幸い、この問題に詳しい町田元君と山﨑秀記君（どちらも東大での教え子で、一橋大学名誉教授）に原稿を見ていただき、懇切丁寧なご教示をいただいたおかげで、誤りは解消できた、と思う。度重なるメールのやりとりに辛抱強くお付き合いいただいたお二人に、深く感謝したい。

本書のまとめの段階では、講談社の善戝康裕さんにお世話になった。また原稿の細部まで細かく検討された校閲担当の方々にもたいへん有益なご指摘を頂き、感謝している。それでもまだ私が見落とした誤りは残っているに違いないが、そのあたりは読者の皆様のご叱正をお願いしたい。

著者野﨑昭弘（のざき・あきひろ）
1936年、横浜市生まれ。東京大学理学部数学科卒業、同大学院数物系研究科修了。電電公社（現ＮＴＴ）電気通信研究所、東京大学教養学部、同理学部、山梨大学工学部、国際基督教大学教養学部、大妻女子大学社会情報学部、サイバー大学ＩＴ総合学部教授を経て、現在は現役を退き、大妻女子大学名誉教授。専門はアルゴリズム理論、多値論理学、数学教育。ベストセラーとなった『詭弁論理学』（中公新書）をはじめ、『離散数学「数え上げ理論」』（講談社ブルーバックス）、『不完全性定理』（筑摩書房）、『赤いぼうし』（童話屋）、『ゲーデル、エッシャー、バッハ』（共訳・白揚社）など、著書・和訳多数。第3回日本数学会出版賞受賞、『ゲーデル、エッシャー、バッハ』で第22回日本翻訳文化賞受賞。