過去・現在・未来

コロナの年、何をしてきたかまとめてみました。 毎月一回のペースでセミナーを開催しました。 3月以降のセミナーは、全てオンラインでした。 YouTubeの利用を拡大しました。 MaruLabo Top Page    (MaruLaboサイト) Maruyama Lectures 　(YouTubeサイト) 21/02/26 マルゼミ「 チューリングマシンの拡大と複雑性理論 」 20/01/29 マルレク基礎「 チューリングマシンを学ぼう！ 」 20/12/25 マルゼミ「 MIP*=RE入門 」 20/11/27 マルレク「 コンピュータサイエンスの現在 — MIP*=RE定理とは何か 」 20/10/15 マルレク「 量子コンピュータ入門 — 量子コンピュータと人工知能 」 20/09/18 マルレク「 人工知能と計算科学 」 20/08/28 マルゼミ「 量子通信入門 」 20/08/18 公開資料 「 MIP*=RE References 」 20/07/26 マルレク基礎「 エンタングルメントで理解する量子の世界 」 20/06/30 楽しい数学　「 2のn乗の話（チューリングマシンの話） 」 20/06/20 マルレク基礎「 ケット|k> で理解する量子の世界 」 20/05/15 マルレク基礎「 たとえ話で理解する量子の世界 」 20/05/05 マルレク「 AWSでの形式手法の利用 」 20/03/27 マルゼミ「 論理学入門 II — ラムダ計算と関数型言語 」  20/02/17 マルレク「 量子コンピュータの現在 — 量子優越性のマイルストーンの達成 」 20/01/28 マルゼミ「 論理学入門 I 」 19/11/28 マルレク「I T技術とCoqの世界 –証明 = プログラム = 計算の意味を考える 」 19/11/07 ハンズオン「 はじめてのCoq 」

先に見てきたのは、図の左側の n-exponential な時間で「検証可能」な複雑性を考えて、複雑性概念を拡張すると、ついには、「帰納的可算」のクラスに至るという話である。 n-exponential な数は、たとえそれがどんなに巨大なものであっても、有限な自然数であることに変わりはない。ただ、その有限の「無限」な連鎖の果てに、良く定義されたある意味自然な概念が、改めて、たち現れるのだ。 振り返ってみよう。 我々は、無限のものを認識できない。まず、認識の対象を形式的に有限な手段で定義可能なものに限る。「帰納的可算」というのは、そうした概念である。ただ、そこには、キチンと定義はできても、計算不可能だったり証明できないものが含まれる。 それで、「帰納的可算」の概念に手を入れ、キチンと定義され、かつ、計算可能なもの・証明可能なものを「帰納的」なものとして再定義する。「チューリング・マシンで実効的に計算可能なものが、計算可能である。」という「チャーチ・チューリングのテーゼ」は「計算可能性理論」（それは、「計算不可能性理論」でもあるのだが）の、ある意味、完成形である。 ただ、この「チャーチ・チューリングのテーゼ」の定義に従えば、「計算可能」であるはずなのだが、現実的には、どうしても計算できないものがたくさんあることに気付く。こうした実際には手に負えないものを、現実的に計算可能なものとを区別しようという動きが生まれる。「計算複雑性」の理論誕生の背景は、そうしたものだと思う。 こうして、「多項式時間」で計算できるものと、「多項式時間」では計算できないものとを区別しようという一つの基準が導入される。この基準は、ある意味合理的なものであった。1970年代に登場した複雑性理論は、コンピュータ・サイエンスの中心分野の一つとして発展し、成功する。それはいいことだ。 ただ、悪いニュースもある。いつの間にか、計算を科学する様々な分野に、次のような考えが生まれてくる。それは、もとの「チャーチ・チューリングのテーゼ」を修正した、「チューリング・マシンで多項式時間で計算可能なものが、計算可能である。」という考えが、「計算可能性」の定義として広まりはじめたことだ。それを「拡大されたチャーチ・チューリングのテーゼ」という。 「拡大されたチャーチ・チューリングのテーゼ」が、おそらく「誤り」であるだろうと

前回、次のような、二つの対をなす複雑性のクラスを三つほど見てきた。  1.   NP        \(O(3^n)\)の証明時間               P         \(O(n)\)の検証時間   2.  NEXP     \(O(3^{2^n})\)の証明時間         EXP      \(O(2^n)\)の検証時間   3.  NEEXP   \(O(3^{2^{2^n}})\)の証明時間         EEXP    \(O(2^{2^n})\)の検証時間  一つ確認しておきたいのは、2番目の NEXPクラスは、NPクラスではないということである。NPクラスは、証明のの検証が多項式時間で終わるクラスのことだが、このNEXPクラスは、検証に指数関数的時間を要するクラスである。多項式時間では、このクラスの検証は終わらない。 同様に、3番目のNEEXPクラスは、NPクラスでもNEXPクラスでもない。それは、証明の検証に、はるかに長い時間を必要とする、それらよりずっと複雑なクラスである。 形から見れば、NP, NEXP, NEEXP, ...という延長上に、NEEEXPなり NEEEEXP ... といった複雑性クラスを考えることができそうである。また、それは、大きな認識の飛躍のようにも思えないかもしれない。 結果的には、確かにそうなのだが、そうしたアイデアは複雑性理論の中で、最初から「自然」に生まれたものではないことには注意が必要である。そのことは、複雑性理論の歴史を振り返ればわかる。 歴史的には、1番目の NPクラスとNP-完全の概念の定式化は、1971年の CookとLevinに遡る。この間紹介してきた「グラフの3色塗り分け問題」がNP-完全であることを示したのはKarpで1972年のことだ。1970年代初頭は、複雑性理論の創世記である。 2番目のNEXPクラスの特徴づけがなされ、その基本的な性質が解明されたのは、BabaiとFortnowとLundが、NEXP = MIP を証明した時である。MIPはMulti-Prover Interactive Proof である。1991年のことだ。1990年代、Interactive Proofの手法の導入によって、複雑性理論は新しい段階に入る。 3番目のNEEXPクラスの特徴づけをあたえたのは

n個の頂点を持つグラフが3色で塗り分けられるかという問題は、代表的なNP-完全問題である。n個の頂点が3色に塗られたグラフは、\(3^n\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、容易ではない。この問題への答えが「YES」であることを示すこと、すなわち、このグラフが3色の塗り分けを持つことを「証明」するのは「むずかしい」。 ただ、その「証明」は、「これがこのグラフの3色の塗り分けだ」という形をしているはずである。こうした「証明」が与えられた時、その「証明」が「正しい」か否かの「検証」は、n個の頂点が「塗り分け」の条件を満たしているかのチェックで、多項式時間で可能である。その「検証」は、元のNP問題より「やさしい」問題で、多項式時間のクラスPに属する。 こうした、PとNPの関係を拡張して、次のようなクラスを考えることができる。 \(2^n\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考える。\(2^n\)個の頂点が3色に塗られたグラフは、\(3^{2^n}\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、もちろん容易ではない。この問題の複雑性クラスをNEXPと呼ぶ。 なぜ、NEXP（それは"N+EXP"だ）という名前がつくかは、次のように考えればいい。この問題が「YES」という解を持つなら、「これがこのグラフの3色の塗り分けだ」という「証明」を持つ。この「証明」が正しいことの「検証」は、\(2^n\)個の頂点を一つづつ調べて、それが「塗り分け」の条件を満たしているかチェックすればいい。 それは、\(3^{2^n}\)個のグラフを検索することの「むずかしさ」とくらべれば、\(2^n\)個の頂点のチェックは、はるかに「やさしい」ことだ。この「検証」の複雑性は、\(2^n\) すなわち、EXP(指数関数的時間の複雑性)に属することになる。 もちろん、EXPクラスは、けっして「やさしい」クラスではない。それは、PやNPよりもずっと複雑なクラスである。それにもかかわらず、NEXPクラスの「むずかしさ」と比べると、EXPクラスはずっと「やさしい」クラスなのだ。 同様に、\(2^{2^n}\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考え、その複雑性NEEXPを考え

 【 グラフの３色塗り分け問題 】 先に「リーマン予想」と等価な「グラフの３色塗り分け問題」があると書いたのだが、グラフの問題に置き換えたからといって、問題がやさしくなるわけではないことを、確認しておこう。 グラフの頂点を、{r(赤) , g(緑) , b(青) }の三色で塗る場合の数がいくつあるかを考えよう。 頂点の数が1つの場合には、{r}, {g}, {b}の 3通り、 頂点の数が2つの場合には、{rr}, {gg}, {bb}, {rg}, {gr}, {gb}, {bg}, {rb}, {br} の 9通り. 一般に頂点の数がn個の場合には、\(3^n\) 通りになる。 頂点の数が20個で頂点が3色に塗られたグラフの数は、\(3^{20}\)である。一つのグラフを見つけるのに1nano秒かかるとしてこの操作は、多分、数秒で終わるだろう。 nが大きくなるにつれて、この\(3^n\)は急速に増大する。n=30となると、\(3^{30}\)という数のグラフを枚挙する操作は、\(3^{30}\) nano秒の時間を要する。それは現在の宇宙が生まれてから現在までの時間の100倍以上の時間が必要になる。 n=30程度であっても、総当たりで、三色グラフを全部数え上げるのは、ほぼ、不可能だ。（「リーマン予想」を表現するグラフが、頂点数が30程度ということはないだろう。） ただ、n個の頂点を持つグラフを3色で「塗り分けろ」というのは、同じ色を持つ頂点は辺で結ばれていてはいけないということだ。 だから、もし、誰かが頂点数30のグラフの「3色塗り分け」を与えたとしよう。この時、この「3色塗り分け」が「正しい塗り分け」になっているかの「検証」は、30個の頂点について、その頂点と辺で結ばれている隣り合う頂点が違う色であることをチェックすれば、簡単に終わる。 一般に、n個の頂点からなるグラフでは、一つの頂点に対して、辺で結ばれた頂点は多くてもn-1個しかない。辺で結ばれた頂点の色が違うことのチェックは、 高々、\(n(n-1)/2\)回のチェックで終わってしまう。これは多項式時間で検証可能である。

先の投稿でこう書きました。 「歴史的には、現代の「複雑性理論」は、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-完全であるという認識は、「数学的

　リソースによる複雑性の階層 先に、「複雑さ」を、ある問題を計算するのに必要な時間とメモリーの大きさで分類するというアプローチを紹介しました。 ある時間\(T_0\)では解けないけれど、\(T_0\) より大きな時間 \(T_1\)では解ける 問題、あるいは、ある量のメモリー空間\(S_0\)では解けないけれど、\(S_0\) より大きなメモリー空間 \(S_1\)では解ける 問題を考えて、多くの計算リソース（時間、空間）を要する問題を「複雑な問題」と考えることは自然なことです。また、多くの計算リソースを要する問題を「むずかしい問題」、より少ない計算リソースを要する問題を「やさしい問題」と考えることができます。 こうした「時間複雑性」や「空間複雑性」といった階層が存在することは、ある問題をできるだけ効率的に、短いステップで少ないメモリーで書こうとするプログラマーが、日常的に意識していることです。 一つの問題には、それを解く複数のアルゴリズムが存在しえますので、ある問題にとって、それを解くアルゴリズムの数だけ具体的な実行計算複雑性が存在することになります。例えば、n個のものを大きさ順に並べ替えるSORT問題の実行計算複雑性は、bubble sortのアルゴリズムなら \(O(n^2)\)に、quick sort のアルゴリズムなら\(O(n log n)\)になります。  プログラマにとっての実践的な関心は、その下限を目指すことですが、下限を確定することは、理論的にも実践的にも簡単なことではありません。 　コルモゴロフの「複雑性」 複雑性については、今回のセミナーで扱うアプローチとは別の流儀があります。コルモゴロフは、ある対象の複雑性を「その対象を出力するプログラムの最小の大きさ」で定義します。これは、ある問題を解くアルゴリズムの実行計算複雑性の下限を追求するアプローチと、向いているベクトルはよく似ています。それをもっと抽象化・一般化したものです。 ある問題についての最小のプログラムを「エレガントなプログラム」と呼ぶことにすると、チャイティンは、「あるプログラムがエレガントであることを我々は証明できない」ことを証明しました。これを「チャイティンの不完全性定理」といいます。 これらについては、以前の僕のブログを参照ください。 　●「コルモゴロフの複雑性」 　　　 htt