過去・現在・未来

以前、次のように書きました。 「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と。 それは、人間の認識の歴史について語ったものでしたが、具体的な計算の複雑さの尺度にも、この「長い時間と膨大な知識の集積」に対応する量があります。 それは、「その計算にどれぐらいの時間が必要か？」という時間の尺度と、「その計算にどのくらいのメモリー空間が必要か？」という空間の尺度です。前者を「時間計算量」、後者を「空間計算量」と言います。 チューリングマシンで言えば、「時間計算量」はある計算に必要なチューリングマシンの命令の「ステップ数」に、「空間計算量」はある計算に必要なチューリングマシンの「テープの長さ」に対応します。 決定性チューリングマシンで、\(O(f(x))\)で表される時間計算量の複雑性クラスを\({\bf DTIME}(f(x))\)で表し、同じく空間計算量の複雑性クラスを\({\bf DSPACE}(f(x))\)で表します。 \({\bf DTIME}(f(x)),  {\bf DSPACE}(f(x))\)のままでもいいのですが、代表的な複雑性クラスについては、次のような別名を付けます。ここで\(p(n)\)は、入力の大きさnについての多項式です。 時間複雑性については、 　　\({\bf P} = {\bf DTIME}(p(n))\) ; 「多項式時間」です。 　　\({\bf EXP} = {\bf DTIME}(2^{p(n)})\) ; 「指数関数的時間」です。 　　\({\bf 2-EXP} = {\bf DTIME}(2^{2^{p(n)}})\) ; 「二重指数関数的時間」です。 空間複雑性については、 　　\({\bf PSPACE} = {\bf DSPACE}(p(n))\) ; 「多項式空間」です。 　　\({\bf EXPSPACE} = {\bf DSPACE}(2^{p(n)})\) ; 「指数関数的空間」です。 　　\({\bf 2-EXPSPACE} = {\bf DSPACE}(2^{2^{p(n)}})\) ; 「二重指数関数的空間」です。 この時、 時間計算量では、\({\bf P} \subset {\bf EXP}\) という関係が成り立ちます。空間計算量では、\({\bf PSPACE} \sub

【関数の増大のイメージとBig O記法】 （以下では、「xのn乗」を x^n と表しています。式が読みにくいので、latexが使えるblogに同じ内容を投稿しました。こちらもどうぞ。https://maruyama097.blogspot.com/2021/02/big-o.html　) 先に、「n^2 あるいはnlog(n)に対応した計算複雑性を考えることは、もちろんできます。n^2は、多項式時間のPに属しますが、nlog(n)は、nの多項式ではありません。Pとは別の、nlog(n)という計算複雑性を考えることは可能です。」と書きました。 ここでは、ある関数f(n)が、nが増えるにつれてどのように増大するかを具体的に見ておきましょう。次の図を見てください。 ここでは、次の8つの関数が表示されています。n!,  2^n,  n^2, nlog n, n, √n, log n, 1  n!,  2^n,  n^2, nlog n が nと比べて急速に大きくなることがわかります。それでも、n! > 2^n >  n^2 > nlog nですね。nが大きくなるにつれて、その差はもっと大きなものになります。例えば、n=10の時、 10!は3628800、 2^nは1024ですが、n^2は100、nlog nは、10の自然対数は、2.302... ですので、約23になります。 二つの関数 f(x)とg(x)があって、xがある値以上の時、ある正の定数cが存在して、常に f(x)よりcg(x)が大きい時、f(x) ∈ O(g(x))と表します。これをBig O記法と言います。イメージとしては、関数の値の増大に一番寄与している項を上限として取り出したものです（他の項は捨てます）。関数の定数倍の定数cも捨てます。 例えば、f(x)=4x^3-2x^2+5 という関数のBig O 表記を考えましょう。xが大きくなるにつれてf(x)の値の増大に一番寄与するのは、4x^3の項です。f(x)=O(4x^3)ですが、この定数の部分も省略して、f(x)=O(x^3)と表すことができます。 この表記で、多項式中のnの最大次数をkとして、多項式 poly(n)は、O(n^k)と表すことができます。

先に、「\(n^2\) あるいは\(n \log(n)\)に対応した計算複雑性を考えることは、もちろんできます。\(n^2\)は、多項式時間のPに属しますが、\(n\log(n)\)は、nの多項式ではありません。Pとは別の、\(n\log(n)\)という計算複雑性を考えることは可能です。」と書きました。 ここでは、ある関数f(n)が、nが増えるにつれてどのように増大するかを具体的に見ておきましょう。次の図を見てください。 ここでは、次の8つの関数が表示されています。\(n!,  2^n,  n^2, n\log{n}, n, \sqrt {n}, \log {n}, 1 \) \(n!,  2^n,  n^2, n\log{n} \)が nと比べて急速に大きくなることがわかります。それでも、\(n! > 2^n >  n^2 > n\log{n} \)ですね。nが大きくなるにつれて、その差はもっと大きなものになります。例えば、n=10の時、\(2^n\)は1024ですが、\(n^2\)は100、\(n\log{n}\)は、10の自然対数は、2.302... ですので、約23になります。 二つの関数 f(x)とg(x)があって、xがある値以上の時、ある正の定数cが存在して、常に f(x)よりcg(x)が大きい時、\(f(x) \in O(g(x))\)と表します。これをBig O記法と言います。イメージとしては、関数の値の増大に一番寄与している項を上限として取り出したものです（他の項は捨てます）。関数の定数倍の定数cも捨てます。 例えば、\(f(x)=4x^3-2x^2+5 \)という関数のBig O 表記を考えましょう。xが大きくなるにつれてf(x)の値の増大に一番寄与するのは、\(4x^3\)の項です。\(f(x)=O(4x^3)\)ですが、この定数の部分も省略して、\(f(x)=O(x^3)\)と表すことができます。 この表記で、多項式中のnの最大次数をkとして、多項式 poly(n)は、\(O(n^k)\)と表すことができます。

 複雑性理論で、もっとも基本的なクラスは、「多項式時間で計算可能なクラス P」です。このクラスは、人間にとってコンピュータで実際に計算できる計算と、ほぼ同じものです。 「人間にとって」というのが、奇妙におもわれるかもしれませんが、これはこれで大事なことです。見かけは単純に見える問題でも、アルゴリズムによっては、その計算には信じられないほど長い時間がかかる計算があります。人間は、多分、計算終了まで待つことができません。 だいぶ前になりますが、一部では話題になった動画があります。「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」 https://www.youtube.com/watch?v=Q4gTV4r0zRs 是非、ご覧になってください。 こうした問題を「数え上げ問題」というのですが、複雑性理論で個数の数え上げが、重要な意味を持つことを初めて示したのは、日本のコンピュータ・サイエンティスト 戸田誠之助 氏です。彼は、日本人で唯一人のゲーデル賞の受賞者(19998年)です。

ここでは複雑性理論での「多項式時間」について話してみようと思います。 \(xもx^2もx^3もx\)の多項式です。もっと一般に、\(a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n \)の形の式を「xの多項式関数」と呼びます。それぞれの項が、\(x^n\)に係数\(a_n\)が掛かった形をしていて、それらの和で表される関数です。xの多項式関数を\(poly(x)\)で表します。 ただ、\(2^xや3^x\)は、xの多項式とは呼びません。\(a^x\)は、aについてみればaの多項式ですがxについてみればxの多項式ではありません。変数xが「x乗」の形である項の肩に現れる関数を「xの指数関数」と言います。 複雑性の理論では、多項式時間で計算される問題のクラスを Pで表します。 ただ、いくつか注意すべきことがあります。 第一に、何についての多項式かを決めておく必要があります。1+1よりは、1000+1000の方が計算には時間がかかります。一般に、入力に与えられるデータが単純なものより複雑なものに計算には時間がかかるはずです。入力の大きさをnで表した時、計算時間をnの関数\(f(n)\)で表します。「多項式時間で計算される」というのは、入力の大きさをnとする時、その計算時間が、多項式\( poly(n)\)で表せるということです。 第二に、注意すべきことは、計算量を時間ではかるには、二つのやり方があるということです。一つは、実際に実行時間を実時間ではかるやり方です。もう一つは、たとえて言えば、コンピュータで何クロックその処理にかかるのかをはかるやり方です。 複雑性理論での時間計算量は、後者のアプローチをとります。計算を、基本的な要素に分解して、その基本操作の何ステップで処理が終わるかで、時間をはかります。正確な定義は後で述べますが、直感的にいうとチューリングマシンの一命令の実行を時間の単位にします。 そうすると面白いことが起きます。 ある問題が多項式時間で計算される複雑性のクラスPに属するとします。ムーアの法則で、コンピュータの処理速度が指数関数的に増大したとしても、基本動作が早くなるだけで、処理に必要なステップが短くなる訳ではありません。ですので、実際の実行時間がいくら速くなっても、その問題が多項式時間のクラスPに属することに変わりはありません。 もっと面

私たちの認識は単純なものから複雑なものに進みます。世界は複雑なものであふれているので、我々の認識もどんどん複雑になっていきます。ただ、こうした私たちの認識の前進がいつまでも続くとは限りません。私たちの認識は、しばしば、複雑さの前に立ちすくみます。複雑なものを理解するのには、長い時間と膨大な知識の集積が必要であることは、科学の歴史を見れば分かります。 僕は、対象の複雑さと認識の複雑さは同じものだと考えています。そうした認識は「複雑さ」そのものを対象とした認識が可能だということを意味します。現代の計算科学のもっとも活発な研究分野はの一つは「複雑性理論」なのですが、そうした理論が登場したことの意味は、そう考えれば、よく理解できると思います。 今回のセミナーでは、様々なチューリングマシンの拡大と複雑性のクラスの対応を紹介したいと思います。次のようなチューリングマシンを取りあげます。 https://turing-complex.peatix.com/view 　● 決定性チューリングマシン 　● 非決定性チューリングマシン 　● 確率性チューリングマシン 　● 量子チューリングマシン 先に、「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と書きましたが、このチューリングマシンによる複雑さのモデルでは、複雑なものを理解するのに必要な「長い時間」がチューリングマシンの「計算時間」に、「膨大な知識の集積」がチューリングマシンの「テープの長さ」に対応すると思って構いません。 「そんな単純化で大丈夫か？」 確かに。 もちろん、科学の歴史をチューリングマシンに喩えようと思っているわけではありません。ただ、こうした単純化（「抽象化」は、単純化に他なりません）された切り口が、「認識の有限性と対象の無限性」「古典論と量子論」「決定論と確率論」といった認識の大きな問題にアプローチする一つの有効な手段を提供するという話ができればと思っています。

有限と無限は対の概念です。英語でも、"finite"と "infinite" と対になっていますね。ただ、有限と無限の対比の仕方は、日本語と英語とでは、少し違います。日本語では、有限は「限界があるもの」で、無限は「限界がないもの」ですが、英語では、「無限」は「有限でないもの」です。日本語の方が、定義が踏み込んでいます。 ここでは、「限界がある」という有限の定義で、有限には、どんな限界があるのかを考えてみましょう。 有限の身近なモデルとして、自然数を考えましょう。ある具体的な自然数nを考えて、nは有限であると考えることは自然なことのように思われます。具体的な自然数を有限のモデルだとして、今度は、有限の「限界」を、どんな自然数nに対しても、n < N なるNが存在することだと考えましょう。有限な自然数には、大きさで超えられない壁があって、それが有限の「限界」だと考えるということです。 ただ、この有限の「限界」の特徴づけは、いくつか奇妙なところがあります。 限界Nが存在して、それが自然数だとします。その時、N+1も自然数で、N < N+1 ですので、限界はNではなく、N+1になります。これは矛盾です。ですから限界Nが、自然数だと考えることはできません。これは、素直に考えれば、最大の自然数は存在しないということです。また、それは、具体的に与えられた自然数nより大きい自然数は「無限」に存在することを意味します。 先に、ユークリッドが素数が無限に存在することの証明を、無限という言葉を使わずに行ったと書きましたが、彼が行ったのは、次のような証明です。基本的には、上と同じ論理です。 最大の素数pが存在するとする。p以下の全ての素数の積に1を加えた数をPとする。Pは、全ての素数で割っても、1が余って割り切れない。よってPは素数で、p < P で、pは最大の素数ではない。これは矛盾。よって、最大の素数は存在しない。 色々奇妙なところもあるのですが、「具体的に与えられた自然数＝有限」というモデルを維持することにこだわりましょう。このモデルは、自然なものにおもえますので。 それでは、この有限のモデルで、その「限界」は、どう考えればいいのでしょう？ 次のようなωを考えます（先に見たように、ωは自然数ではありません）。 　 　「全ての自