「NP-完全」問題 -- 僕の反省

先の投稿でこう書きました。

「歴史的には、現代の「複雑性理論」は、NPという複雑性のクラスと「NP-完全」という概念の発見によって始まります。」

複雑性理論の歴史については、以前、角川さんで行った「人工知能を科学する」という連続セミナーの第一回「人工知能と複雑性理論」https://www.marulabo.net/docs/20180927-kadokawa/ で詳しく触れています。

NP-完全については、この連続セミナーの第三回で、「人工知能と量子コンピュータ — NP-完全問題とその含意」というテーマでお話しをしました。https://www.marulabo.net/docs/20181119-kadokawa/　

これらの資料を読んでいただければと思います。

ただ、残念なことにい、3年前の僕の認識には、いくつかの点で不十分なところがありました。

例えば、「数学とNP問題」というブログで、こう書いています。https://maruyama097.blogspot.com/2018/09/np.html

「ただ、こうした考えに立って、数学の証明の「正しさ」が、多項式時間で「検証可能」だということは、数学の証明可能な問題全体が、NPクラスに属するということにならないか？

な、わけはない。（とも、思うのだが。）」

「な、わけはない。（とも、思うのだが。）」と思っていたのが間違いでした。最初の直感に従って進めばよかったのですが、自分で打ち消しています。多項式長の証明を持つ数学的命題の全体は、NP-完全の代表的な例だということを、僕は、Irit Dinurの講演を聴いて確信しました。

こうした認識に従えば、NP-完全な問題は、すべて共通の単一のアルゴリズムに「還元」できますので、もしも、ある人が、リーマン予想を証明したとすれば、その証明がどんなに長いものだったとしても、その証明に対応したグラフの3色塗り分け問題があることになります。

つまり、少し複雑なグラフでしょうが、そのグラフのノードを3色に塗り分けられることを示せば、リーマン予想を解くことができるグラフがあるということです。

「な、わけはない」

と思ってはいけないのです。「NP-完全」というのは、そういう性質を持つのです。それに、多項式長の証明を持つ数学的命題の全体は、NP-完全であるという認識は、「数学的証明」そのものの特徴づけに、とても大きなインパクトを与えます。

僕の反省は、まだまだ続くのですが、少し弁解させて貰えば、それは3年前に僕が書いたことが、間違いだったということでは、必ずしもないのです。それは、ある意味「間違ってはいないかもしれないが、狭い見方」だったと思っています。ただ、「狭い見方」にとらわれていると、理論の進歩に取り残され、いつか間違いを犯します。

個人的には、この間、MIP*=REの証明を追いかけていて、僕の複雑性理論の見方は、大きく変わりました。今なら、複雑性理論の「歴史」についても、NP問題の「特徴づけ」についても、3年前とは違った説明をするだろうと考えています。

3年前、複雑性について僕の関心の中心は、「量子コンピュータが多項式時間で解く複雑性のクラスBQPは、古典的なコンピュータが多項式時間で解く複雑性のクラスPより広いこと」と「それにもかかわらず、NP-完全問題は量子コンピュータでは解けない」ことに向けられていましたが、そうした関心も、いささか狭いものです。

量子複雑性の主要な担い手は、必ずしも、複雑性BQPで特徴付けられる量子コンピュータではなく、無数のエンタングルメントで結合された量子デバイスのインタラクティブな相互作用の中にあります。