20世紀、コンピュータの世界は急速に進化・発展し、コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。
アルゴリズムと計算量の理論から生まれた、多項式時間(P)で解けるとはどういうことか？
そして、非決定性多項式時間(NP)で解けるとはどういうことか？
今回紹介するのは、以前取り上げたミレニアム懸賞問題の一柱｢P＝NP問題｣について、コンピュータ科学とアルゴリズム理論の歴史も踏まえて分かりやすく解説している書籍である。
なお、ミレニアム懸賞問題およびP＝NP問題については以前の記事を参考されたし。
ここで注目して欲しいのは、｢P＝NP問題｣でなく｢P≠NP問題｣と表記している点だ。
作者曰く、ちまたにはP≠NP問題について実にひどい解説書が出回っており、それによる誤解を予防・解毒したい思いがあるとのこと。
そんな本書のポイントを3つ挙げるとすれば、
① ｢NP｣はNon-polynomial (非多項式)ではない！
② NPは｢具体的な解を確認すること｣ではない！
③ ｢P＝NP｣だとしても、どんな問題も美しく速く解けるわけではない！
さてさて、これらをかいつまんで説明していこう。
解毒：Non-deterministic polynomial time (非決定性多項式時間)
｢P｣はPolynomial time (多項式時間)の略称である。それは間違いない。
しかし、｢NP｣はNon-polynomial time (非多項式時間)ではなく、Non-deterministic polynomial time (非決定性多項式時間)である。
ついでながら、 Polynomial time (多項式時間)で解ける問題のクラスとNon-polynomial time (非多項式時間)で解ける問題のクラスが等しくないことは明らかであり、既に証明されている。
ここで、Non-deterministic polynomial time (非決定性多項式時間)とは、以下の3つの条件を許すアルゴリズムで多項式時間で解ける問題のクラスを表す。
① 非決定論的(Non-deterministic)な選択を許す ② 計算量は最も運が良い場合で考える ③ 答えがNOの場合は、無視してよい
これら条件を許す｢非決定性アルゴリズム｣をしっかりと理解することがNP問題を理解する肝になるわけだ。(詳細については割愛するので本書を参考されたし。悪しからず。)
解毒：具体的な解を求めることだけがNPクラスではない
よくある誤解で、PとNPとの差は
NP：他人に解(の候補、コロンブスの卵)を見せてもらって、それがたしかに解であることを確認する P：自分で解を作る
…というものがある。
しかし、例えば｢素数か否か｣を判定する高速アルゴリズム(AKSアルゴリズム)、言い換えれば｢合成数かどうか｣を判定するアルゴリズムでは、｢素数であるための必要十分条件｣をチェックしており、それによって｢約数(もしあれば)を必ず、具体的に求める｣ことはできない。
つまり、解が｢存在する｣ことと｢具体的に求める｣ことは違うのである。
そうでなければ、例えばある暗号化方式(RSA暗号)では
ある数Nが合成数である(しかも、2つの素数p,qの積である)ことは既にわかっているのに、その素数の値がわからない
…これを安全性の根拠にしているのに、実際の約数pとqがわかってしまったら暗号は解読され、秘密は守れなくなってしまう。
まとめると、クラスNPの問題には｢解が存在すること｣を示すだけのものも含まれるのだ。
解毒：P＝NPでも、原理的に解けない問題もある
｢P＝NPという美しい世界｣では、どんな問題でも速く解けるようになるのだろうか？
例えば、ミレニアム懸賞問題もすべて解けるので、P＝NPを証明すれば賞金100万ドルがもらえ、さらに他の問題も解いて500万ドルもらえるのか？
答えは｢NO｣であり、これはとんでもない誤解である。
まず｢どんな問題でも｣というが、｢原理的に解けない問題｣もある。
したがって、｢クラスNPに属するどんな決定問題でも｣と限定する必要がある。
また、ミレニアム懸賞問題のいくつかにあるような｢証明可能性の判定｣は一般的には不可能な超難問であり、しかもNPには属していない。
だから、P＝NPであろうとなかろうと、個々の問題の証明の難しさには全く関係ないのだ。
それでは、｢P≠NP問題｣がなぜ重要なのか？
作者の考えでは、応用上の意味よりも、理論的な意味のほうが大きいとのこと。
つまり、
これを解くためには、これまでと違った理論が必要
…という点が重要なのだ。
フェルマーの最終定理を解くためには300年を超える数学の発展が必要だった。
ギリシャの3大難問を解くには、群論を創始したガロアの天才や、｢円周率πは超越数である｣ことを証明したリンデマンの業績など、2000年を超える歴史が必要であった。
｢P≠NP問題｣のような難問は、理論の発展にすばらしい刺激を与えてくれるのである。
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
ここで紹介したのはおすすめ書籍に関する概要とP≠NP問題のほんの一部である。
もっと知りたいと思ったら、本書を一読して、｢数学の森｣の奥深くに進んでみよう。
目指せ！！数学の愛人(笑)！！これぞ賢者への道程！！
コメント