第 3 回計算量理論

本日の内容

3-1. 計算の理論と Church の提唱
3-2. 計算量理論の手法
3-3. 計算時間
3-4. Turing 機械の時間計算量
3-5. C のプログラムの計算量
3-6. 次週の予告

3-1. 計算の理論と Church の提唱

問題の難しさ、複雑さを考えるために、Turing 機械を利用します。たとえば、最大級に難しい問題としては Turing 機械でプログラムを組めないような問題を考えることができます。また、それよりやさしい問題、つまり Turing 機械でプログラムを組める問題であっても、計算ステップ数がどれくらいかかるかで比較が可能になります。

プログラムが組める組めないを議論する理論は計算可能性理論と呼ばれています。また、プログラムの計算ステップ数を議論する理論は計算量理論と呼ばれています。

プログラムが存在することを示すには次のような手法があります。

実際にプログラムを作る
プログラムが存在することを示す
Church の提唱(仮説)を利用する

Church の提唱とは「人間が計算可能な問題と、コンピュータ(Turing 機械)が計算可能である問題は等価である」ということを主張するものです。これ自体、証明は不可能で非数学的な主張ですが、人間は Turing 機械の動作を把握することができる一方で、人間が問題の計算の仕方を説明できるのであればそれは Turing 機械でもプログラムが組めるであろうという信念はなんとなく同意できるものです (Turing 機械で自由にプログラムが組めるようになればわかるようになります)。

Church の提唱は、問題の複雑さを議論するのになぜコンピュータを使うのかという問いに答えていますが、それだけではありません。コンピュータのプログラムを作ることによる証明を行う際、人間がどのように解くかを説明することにより、プログラムが作れることと等価とみなし、証明においてプログラムを完璧に作ることを省略できます。

例3-1

関数 $f_{1}$ , $f_{2}$ を計算する Turing 機械 $M_{1}$ , $M_{2}$ が存在するなら、合成関数 $f_{2} \circ f_{1}$ を計算する Turing 機械 $M_{3}$ が存在する。

これは、入力 $x$ に対して $y = M_{1} (x)$ を計算し、さらに $M_{2} (y)$ を出力するようなプログラムを書けば良いと言えるため、人間が明確に手順を示すことは可能です。しかし、 $M_{1}$ や $M_{2}$ が実際の Turing 機械だとすると、それらをパラメータとして、任意の二つの Turing 機械から合成関数を出力する新たな Turing 機械 $M_{3}$ を示すことはものすごく煩瑣です。しかも可能であることはまちがいないでしょう。したがって、 Church の提唱を信じるなら冒頭のような説明で計算できると言うことができます。

例3-2

関数 $f$ を計算する C のプログラムを書けるなら、 $f$ を計算できる Turing 機械を構成できる。

これは、 C で計算が可能なら人間でも計算が可能なので Turing 機械でも計算が可能であるということです。

つまり、 Turing 機械はあらゆるコンピュータ言語と等価の計算能力(可能か否か)を持ちます。

なお、Church の提唱は計算の複雑さについては何も言ってません。それはつまり人間は Turing 機械と同じようには思考しませんので、考え方の効率は異なって当然だからです。

なお、今後は計算量の議論をする時でさえも Turing 機械の直接的なプログラムの例示は必要最小限度にとどめ、日本語や ALGOL のような簡易のプログラミング言語による説明をすることがあります(まだ変数の処理などをどうするか教えてないので、その辺は説明します)。

3-2. 計算量理論の手法

問題の難しさを議論するため、コンピュータ(Turing 機械)を使用します。問題同士の比較をするのに計算量理論は次のような手法を使用します。

計算時間、メモリ使用量など

特定の問題については実際にプログラムを作成することができます。その際は、その問題を解く Turing 機械が計算に何ステップかかるかなどを問題の複雑度とします。 Turing 機械が計算をするのに必要なステップ数を時間計算量と言い、Turing 機械が計算をするのに必要なテープの升目の数を領域計算量と言います。

還元可能性(reducibility)

問題 A が問題 B に変形でき、問題 B が解決すれば問題 A も解けてしまうような状況では問題 A は問題 B ほど難しくないと言えます。これを還元可能性と言います。

例えば、10進数の表現が与えられたとき、偶数か奇数かを判定する問題を考えます。これは実際に 2 で割り算するまでもなく、下ひと桁の偶奇を判定すればわかります。この場合、偶数奇数の判定が、下ひと桁の偶奇の判定問題に還元されたことになります。このことから、偶数奇数判定は下ひと桁の偶数奇数判定ほど難しくないことがわかります(逆も成り立つので、この場合は難しさが等価であると言えます)。

なお還元可能性は実際解けない問題に対しても使用することができます。問題 A が解けない問題だとします。この時、問題 A を変形して問題 B に帰着できたとします。つまり「インスタンス x が A に含まれるかどうか」と「インスタンス y が B に含まれるかどうか」が同値になるように x から y の変形方法を与えることができるとします。その時、問題 B が解けるとすると上記のように問題 A まで解けてしまいます。これは A が解けない問題だという前提に矛盾します。そのため、このようなインスタンスの変形可能性を示すだけで問題 B が解けないことを証明できることになります。

オラクル(神の啓示)

問題 B を解くサブルーチンが存在する時、それをサブルーチンとして問題 A が解けるなら問題 A は問題 B ほど難しくないと言えます。もし B を解く神様が存在したら A を解くのは容易になるという意味で「A は B をオラクルとすれば解ける」と言うときがあります。これは、問題の変形と違い、人間に解くことが不可能な問題を解く仕組みを仮定するからです。なお、これは問題の変形と違い、A を解くのに何度も B のサブルーチンを使うので上記の還元可能性よりは条件が緩くなっています。

3-3. 計算時間

プログラムの計算時間の比較を行うにあたって、かけ算のプログラムを考えてみます。

二進数の値 $x$ と $y$ に対してかけ算 $x \times y$ を行うのに次の二つの計算の仕方を考えます。

$x$ を $y$ 回足す
筆算を行なう

まず、1 の複雑さでは $x$ を $y$ 回足すと言うことで、 $y$ に比例した計算時間がかかると言えます。一方、 2 では筆算ですので、 $x$ の桁を一つずつずらし、高々 $y$ の桁数個分の足し算をするだけでかけ算が計算できます。 $log y$ は桁数に比例しますので、計算時間は $log y$ に比例すると言えます。このように同じも問題でも計算速度の異なるプログラムを作ることができます。また入力の長さに対して計算時間の比例関係を議論することもできます。

一方で、プログラムの細工を考えてみましょう。かけ算プログラムにおいて、特定のかけ算だけ高速化することができます。つまり、特定の入力に対して、あらかじめ計算しておいた結果を表示することによりその計算を一瞬(入力の判断のみ)で終らせることができます。もし、インスタンスが有限個であったら全ての計算をあらかじめしておいて、瞬時に答を出すことが可能になります。これは有限個のインスタンスを対象にした計算量の議論は問題の複雑さとは関係ないことになります。したがって、有限の場合を無視するような議論をしなければなりません。

さらに後に示しますが、「どんなプログラムの計算時間でも定数倍ならいくらでも速くできる(線形加速定理)」があります。これにより、従来より 5 倍速いプログラムなどを構成しても、もともと従来のプログラムを 5 倍速くすることができるので無意味になります。

まとめると、プログラムの速さを議論する時、有限の場合を省き、定数倍の差は無視できるようにする必要があります。

これに対応する数学の概念としてオーダがあります。

$f (n) = O (g (n))$ は、 $f$ の増え方は高々 $g$ 程度を意味し、ある意味 $f \leq g$ のような意味を持ちます。この記号の厳密な定義は次の通りです。

「ある数 $N_{0}$ と $c > 0$ が存在し、全ての $N_{0}$ より大きい数 $N$ に対して $f (N) \leq c g (N)$ が成り立つ」。なお、これは一階述語論理式では次のように書けます。

(\exists N_{0} c > 0) (\forall N \geq N_{0}) [f (N) \leq c g (N)]

では実際にこの記法が上に上げたような良い性質を持つか考えましょう。

不等号的な性質

$n = O (n^{2})$ が成り立ちます。これは $N_{0} = 1$ , $c = 1$ として、 1 より大きいすべての $N$ で $N \leq 1 \times N^{2}$ が成り立つからです。

有限を無視できる

$n^{2} + 1 = O (n^{2})$ が成り立ちます。これは $N_{0} = 1$ , $c = 2$ とすれば 1 より大きいすべての $N$ で $N^{2} + 1 \leq 2 \times N^{2}$ が成り立つからです。

一方で、次の $f (n)$ も $O (n^{2})$ です。

f (n) = {\begin{matrix} 1 & n \leq 10000 \\ n^{2} & n > 10000 \end{matrix}

定数倍を無視できる

$3 n^{2} = O (n^{2})$ が成り立ちます。これは $N_{0} = 1$ , $c = 3$ とすれば 1 より大きいすべての $N$ で $3 N^{2} \leq 3 \times N^{2}$ が成り立つからです。

一番大きい(次数)の項のみを考えれば良い

$2 n^{2} + 3 n + 5 = O (n^{2})$ が成り立ちます。これは $N_{0} = 6$ , $c = 11$ とすれば 6 より大きいすべての $N$ で $2 n^{2} + 3 n + 5 \leq$ $11 \times n^{2}$ $= 2 \times n^{2} + 3 \times n^{2} + 5 \times n^{2}$ が成り立つからです。

この記法をとると、前述のかけ算の例では最初の例は $O (y)$ 回の足し算が必要であり、次の例では $O (log y)$ 回の足し算が必要になります。

3-4. Turing 機械の時間計算量

前回書いた Turing 機械のプログラムの時間計算量を議論しましょう。

Palindrome に対する k-テープ Turing 機械

入力の長さ n に対して、終端記号がそれぞれついているので、入力テープ上のヘッドの移動距離は $n + 2$ になり、それには $n + 1$ ステップかかります。

まず、入力をテープ 2 にコピーするにはテープヘッドを左から右に移動させる必要があるので $n + 1$ ステップかかります。次に一つのヘッドを元に戻すにも同じように $n + 1$ ステップかかります。そして、テープを照合するのにさらに $n + 1$ ステップかかります。結局合計で $3 n + 3$ ステップかかるので、 $O (n)$ ステップと言えます。

Palindrome に対する 1-テープ Turing 機械

左から $k$ 番目の記号は右から $k$ 番目の記号と比較します。その時のヘッドの移動距離は $k$ から $n - k + 1$ までの往復なので、 $2 (n - 2 k + 1)$ となります。これを $k = 1$ から $\frac{n}{2}$ まで行いますので、計算時間は次のようになります。

\sum_{k = 1}^{\frac{n}{2}} 2 (n - 2 k + 1) = \frac{n^{2}}{2} - 4 \frac{\frac{n}{2} (\frac{n}{2} + 1)}{2} + \frac{n}{2}

= n^{2} - n (\frac{n}{2} + 1) + \frac{n}{2} = O (n^{2})

例3-3

最大値を見つけるプログラムの計算量

2 テープ Turing 機械で最大値を見つけるプログラムの計算量を考えます。入力テープには複数の数値が # 記号により区切られ、各数値が二進数のリトルエンディアンで符号化されているとします。一方入力テープでない方のテープを作業用テープと名づけます。この時次のような手順で最大値を見つけるとします。

作業用テープを値が入っていない状態を示すように初期化します
以下を入力テープを読み終えるまで繰り返します
1. 作業用テープに入っている値と入力テープに入っている値で引き算を行い、 (作業用テープの値)-(入力テープの値) で答が 0 以上になっているかどうかを確認します。但し、引き算の結果は残さない物とします。具体的には繰り下がりを状態で覚えることにして、入力テープの値を読みきったときに繰り下がりがあるかないかを判断します。
2. 繰り下がりがある、つまり入力テープの値が大きいと判断したら、その値を作業用テープにコピーします。
3. 入力テープヘッドを次の入力まで移動します
すべての入力を読みきった後に作業用テープに残っている値が最大値になります。

この計算量を求めます。入力の長さを $n$ とし、要素数を $m$ とします。すると、各入力の値の長さ $l_{1}$ ... $l_{m}$ について $l_{1} + ... + l_{m} = n$ が成り立ちます。

さて、上記のプログラムにおいてステップ数のオーダを計算します。

初期化は入力に依存せず定数時間でできますので、 $c_{1}$ ステップ消費するとします。
$j$ 回目の繰り返しにおいて引き算を行う際、入力側が終わってしまえば引き算も終わるので、引き算に必要なステップ数は高々 $l_{j}$ ステップ。そこで、コピーが必要であればコピーを行うが、入力をコピーすることを考えると、コピーする長さは高々 $l_{j}$ 。テープヘッドを戻したりする作業などを入れてもこの数倍程度なので、 $j$ 回目の繰り返しでは $c_{2} l_{j} + c_{3}$ ステップ消費すると考えることができます。

以上により、このプログラムの実行ステップ数は $c_{1} + \sum_{j = 1}^{m} (c_{2} l_{j} + c_{3}) = c_{1} + c_{2} n + c_{3} m = O (n)$ です。

演習3-1

カッコ言語の時間計算量を議論しなさい。

3-5. C のプログラムの計算量

さて、本講義では基本的には特定の問題の計算量を議論するとき、その問題を解く Turing 機械のステップ数を考えます。しかし、我々は通常 Turing 機械を使って問題を解いたりしません。そこで、一般のプログラミング言語でも計算量の計算ができると便利です。なお、Turing 機械と一般のプログラミング言語の計算量の関係については次回に説明します。

例3-4

次のプログラムにおいて、計算速度を考えましょう。

プログラム


#include <stdio.h>
#include <stdlib.h>
int* getIntArray(int count, char *arg[]){
  int i;
  int* array = malloc(sizeof(int)*count);
  for(i=0; i<count; i++){
    array[i]=atoi(arg[i]);
  }
  return array;
}
void bubble(int count,int* arg){
  int i,j;
  int temp;
  for(i=0; i<count; i++){
    for(j=i+1; j<count; j++){
      if(arg[i]>arg[j]){
	temp = arg[i];
	arg[i] = arg[j];
	arg[j] = temp;
      }
    }
  }
}
void print(int count, int* arg){
  int i;
  for(i=0;i<count;i++){
    printf("%d ",arg[i]);
  }
  printf("\n");
}
int main(int ARGC, char *ARGV[]){
  int *array;
  array = getIntArray(ARGC-1,&ARGV[1]);
  bubble(ARGC-1,array);
  print(ARGC-1,array);
  free(array);
  return 0;
}

各行が 1 ステップで計算できるとき

始めに簡単のために、各文が 1 ステップで計算できると仮定しましょう。実際、 C 言語で小規模で実用的な計算を行う場合、int 型の数値などは 1 ステップで計算できるとしても大きく外れてないようです。

main

main ではコマンドの引数の個数を ARGC、引数の文字列の配列が ARGV になっています。入力の長さは ARGV に含まれるすべての文字数ですが、これを $n$ で表すことにします。すると、次が成り立ちます。

ARGC = O (n)

ARGVに入っているそれぞれの数値の桁数 = O (n)

main の実行時間は getIntArray の実行時間と、 bubble の実行時間と print の実行時間と free の実行時間の和になります。オーダの計算をするので、各時間の和に関しては、すべてを求める必要は無く、最悪のオーダーを持つものが見つかればそれが main の実行時間のオーダになります。

getIntArray

getIntArray は与えられた引数リストを元に、整数の配列を作成するものです。 count は配列 arg の要素数を表します。まず、i の宣言、 array の宣言、 malloc の実行はすべて 1 ステップだと考えます。次に、 for 文ですが count 回 atoi を繰り返します。このステップ数は $O (count)$ になります。

bubble

bubble では内側のループの繰り返し回数は count-1, count-2, ... ,0 となっているため、繰り返し回数は以下のようになります。

\sum_{i = 0}^{count - 1} i = \frac{count (count - 1)}{2} = O ({count}^{2})

print

print ではループが count 回繰り返し、各要素が表示されます。但し、すべての arg に入っている要素が出力されるため、ループなどと考えずに、すべての要素を単に出すだけと考えると $O (n)$ になります。

まとめ

以上により、各関数の実行ステップのオーダはそれぞれ次のようになります。

getIntArray: $O (count) = O (n)$
bubble: $O ({count}^{2}) = O (n^{2})$
print: $O (n)$
main: $O (n) + O (n^{2}) + O (n) = O (n^{2})$

したがって、このプログラムの時間計算量は $O (n^{2})$ となります。

数値計算で計算時間が桁数に依存するとき

Turing 機械では一度に定数 bit の情報しか扱えませんでした。したがって、足し算などを行うにも桁数分のステップ数が必要でした。そういう点では、この数値計算で桁数を勘案するというのは、本来の計算量の定義に近い分析になります。

main

main に関してはほぼ同様です。但し、 ARGC-1 を実行しているので、ここで $O (log n)$ ステップ消費します。

getIntArray

getIntArray では sizeof(int)*count や malloc の処理ではそれぞれ $O (log n)$ ステップかかるとします。一方 for ループの中ですが、 i++ や atoi(arg[i]) に関しても $O (log n)$ ステップかかるとすると、 count 回繰り返すので、全体の時間計算量は $O (n log n)$ となります。

bubble

bubble でも同様に、ループ変数の処理、 if の条件、変数の代入などで $O (log n)$ かかるとすると、繰り返しにより全体で $O (n^{2} log n)$ となります。

print

printf で文字列を出力する時は、実行時間は文字列の長さに比例するものとします。さて、ループなどの取扱いが簡単なように、 ARGV の各要素は同じ長さとします。つまり、一つの長さは $\frac{n}{m}$ であるとします。この時、各繰り返しでは i に 1 を加える処理と、出力を行います。そのため、一回で必要なステップ数は $O (log m) + \frac{n}{m}$ となります。これを $m$ 回繰り返しますので、 $m (O (log m) + \frac{n}{m}) = O (m log m + n) = O (n log n)$

まとめ

以上により、各関数の実行ステップのオーダはそれぞれ次のようになります。

getIntArray: $O (n log n)$
bubble: $O (n^{2} log n)$
print: $O (n log n)$
main: $O (n log n) + O (n^{2} log n) + O (n log n) = O (n^{2} log n)$

したがって、このプログラムの時間計算量は $O (n^{2} log n)$ となります。

演習3-2

以下のプログラムの時間計算量を次のそれぞれの条件の元で求めなさい。

各命令が 1 ステップで行われるとき
自然数の計算において、足し算、 2 倍などが $O (log n)$ 、掛け算や割り算は $O ((^{log n) 2})$


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int* createArray(int x){
  int i;
  int* array;
  array = malloc(sizeof(int)*x);
  for(i=0; i< x; i++){
    array[i]=1;
  }
  return array;
}
void sieve(int x, int* array){
  int i,j; 
  for(i=2;i<sqrt(x);i++){
    if(array[i]){
      for(j=i*2;j<x;j+=i){
	array[j]=0;
      }
    }
  }
}
void print(int x, int* array){
  int i;
  for(i=2;i<x;i++){
    if(array[i]){
      printf("%d ",i);
    }
  }
  printf("\n");
}
int main(int ARGC, char *ARGV[]){
  int x;
  int i,j;
  int *array;
  x = atoi(ARGV[1])+1;
  array = createArray(x);
  sieve(x,array);
  print(x,array);
  free(array);
  return 0;
}

3-6. 次週の予告

次週は万能 Turing 機械についてお話します。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 3 回 計算量理論

本日の内容

3-1. 計算の理論と Church の提唱

例3-1

例3-2

3-2. 計算量理論の手法

3-3. 計算時間

3-4. Turing 機械の時間計算量

Palindrome に対する k-テープ Turing 機械

Palindrome に対する 1-テープ Turing 機械

例3-3

最大値を見つけるプログラムの計算量

演習3-1

3-5. C のプログラムの計算量

例3-4

プログラム

各行が 1 ステップで計算できるとき

main

getIntArray

bubble

print

まとめ

数値計算で計算時間が桁数に依存するとき

main

getIntArray

bubble

print

まとめ

演習3-2

3-6. 次週の予告

第 3 回計算量理論