第 3 回 計算量理論

本日の内容

• 3-1. 計算量理論
• 3-2. 計算量理論の手法
• 3-3. 計算時間
• 3-4. 前回のプログラムの時間計算量
• 3-5. 次週の予告

3-1. 計算量理論

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

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

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

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

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

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

例3-1

関数 f₁, f₂ を計算する Turing 機械 M₁, M₂ が存在 するなら、合成関数 f₁・f₂ を計算する Turing 機械 M₃ が存在する。

例3-2

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

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

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

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

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

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

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

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

還元可能性

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

例えば、偶数か奇数かを判定するには下ひと桁の偶奇を判定すればわかります。 この場合、偶数奇数の判定が、下ひと桁の偶奇の判定に還元されたわけで、 偶数奇数判定は下ひと桁の偶数奇数判定ほど難しくないことがわかります(逆 も成り立つので、この場合は難しさが等価であると言えます)。

なお還元可能性は実際解けない問題に対しても使用することができます。

オラクル(神の啓示)

問題Bを解くサブルーチンが存在する時、それをサブルーチン として問題 A が解けるなら問題 A は問題 B ほど難しくないと言えます。 もし B を解く神様が存在したらA を解くのは容易に なるという意味で「Aは Bをオラクルとすれば解ける」 と言うときがあります。

今日は計算時間を問題の複雑度の比較に使う議論をします。

3-3. 計算時間

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

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

1. x を y回足す
2. 筆算を行なう

まず、1 の複雑さでは x をy回足すと言うことで、 yに比例した計算時間がかかると言えます。 一方、 2 では筆算ですので、x の桁を一つずつずらし、高々 y の桁数個分の足し算をするだけでかけ算が計算できます。 logy は桁数に比例しますので、計算時間は log y に 比例すると言えます。

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

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

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

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

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

「ある数 N₀ と c>0 が存在し、全 ての N₀ より大きい数 N に対して f(N)≦cg(N) が成り立つ」。 なお、これは一階述語論理式では次のように書けます。
(∃ N₀, c>0) ( ∀ N≧N₀) [f(N)≦cg(N)]

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

不等号的な性質

n=O(n²) が成り立ちま す。 これは N₀ = 1, c=1 として、 1 より大きいすべての N で N ≦ 1 ×N² が成り立つからです。

有限を無視できる

n² + 1 = O(n²) が成り立ちます。 これは N₀ = 1, c=2 とすれば 1 より大きいすべての N で N² + 1 ≦ 2 ×N² が成り立 つからです。

定数倍を無視できる

3 n² = O(n²) が成り立ちます。 これは N₀ = 1, c=3 とすれば 1 より大きいすべての N で 3 N² ≦ 3 ×N² が成り立 つからです。

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

2 n² + 3 n + 5 = O(n²) が成り立ちます。 これは N₀ = 6, c=11 とすれば 6 より大きいすべての N で 2 N² + 3 N + 5 ≦ 11 × N² = 2 × N² 3 × N² 5 × N² が成り立つからです。

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

3-4. 前回のプログラムの時間計算量

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

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

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

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

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

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

演習3-1

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

3-5. 次週の予告

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