第 2 回 計算量理論(1)

本日の内容

• 2-1. 前回の復習
• 2-2. 計算量理論(1)

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

2-1. 前回の復習

ポイント

計算可能性理論はコンピュータの計算限界を議論する理論です。 人間の判定能力とコンピュータの判定能力を同一だと見なすチャーチの提唱に より、人間の思考の限界を議論するという哲学的な側面もあります。 ほぼ重要なことは大体判明しています。 「連立整数多項式の整数解存在の判定」というヒルベルトの第十問題は、こ の計算可能整理論により判定不能であることがわかりました。

1. 集合に含まれるか否かをプログラムにより判定できる集合を recursive set と 言う。
2. 集合に含まれる要素に対してだけ計算が停止するようなプログラムが存在 する集合を recursive enumerable set と言う。
3. コンピュータのプログラムは pairing function により単一の自然数に対応 づけられる(Gödel 数)。
4. プログラムの入力にそのプログラム自身を与えたとき、停止するようなプ ログラムの集合を K と定義し、停止問題と呼ぶ。
5. K は recursive enumerable だが recursive でない。
6. many-one reducibility とは集合 A に x が含まれるかどうかを調べるの に、f(x)が B に含まれるかどうかを調べればよいことを示す。但し、 f は recursive funcion。 特に、 f が 1-1 の場合、 1-1 reducibility と言う。
7. Turing reducibility とは集合 B に含まれるかどうかを判定するプログ ラムがあることを仮定すると集合 A に含まれるかどうかを判定するプログ ラムを作ることができることを言う。
8. many-one reducible ならば Turing reducible
9. 任意の recursive enumerable set は K に 1-1 reducible。これを 1-complete と言う。つまり K は recursive enumerable set の中で一番難 しい問題。

2-2. 計算量理論(1)

導入

本章では問題の複雑さを調べます。 但し、この理論で取り扱う「問題」とは問題例(instance)を無限個作れるよう なものです。

例2-1

n は素数か?(n はパラーメータで無限個の可能性を許す)

○

素数は無限個あるか?

×

双子素数(n, n+2) は無限個あるか?

×

問題の複雑さを調べるにはそれを解くのに必要な資源量で議論します。 計算量の調べ方として、 lower bound(必要な資源量)と upper bound(十分な 資源量)と reducibility があります。

資源量として次のようなものが議論されます。

• 計算時間
• メモリの使用量
• 回路のゲート数
• 回路の段数
• 計算に必要な乱数のビット数
• プログラムの長さ

注意

回路は入力の長さごとに構成します。そして、長さをパラメータとした回路の無 限集合を考えます。 この無限集合に対して入力の長さの関数として回路のサイズや段数を考えます。

Lower Bound

Lower Bound はある問題を解くために必要な資源量を求めることです。 これは、その資源量が欠けると解くことができないという不可能性を示す必要 があります。 計算量理論において計算ができないことを示すのは困難なことで、まだ知られ ている結果は少ないです。 但し、暗号理論では安全性として条件を満たす盗聴者には解読できないことを 保証しなければならないため、分野としては重要です。 以下、知られている有名な結果を示します。

Knuth

Sorting(並び替え)を二値の大小比較を使ってプログラムすると、少な くとも c n log n 回の比較をしないといけない。

証明の方針

if 文によりプログラムは 2 通りの計算に分岐します。 そのため、プログラムの流れにおいて、この分岐を木構造に書くことができま す(計算木)。 すると、 if 文はこの計算木の頂点になります。 このうち最も深い path の長さ(頂点数)が、求める必要な分岐数となります。

さて、入力として、 1 から n までを入れる時、並べ方は n! 個あります。 これらを最終的に 1 から n まで順番に並べるためには、全ての入力パターン に対して異なる計算(順序替え)になる必要があります。 k 段の二分木では最大 2^k 個に分岐できるます。 そのため、最終的に n! 個の計算パターンになるためには n!= 2^k つまり、log n! 段が必要です。 ここで以下のスターリングの公式を利用します。

すると、 $logn!\le cnlogn$ となります。

Yao

パリティ(ビット数の偶奇判定)をする定数段の論理回路を作ろうと思う と、入力の長さに対して指数個のゲートが必要となります。

証明

略

Upper Bound

Upper Bound は 具体的なプログラムを与えて、計算量を議論することにより、問題を解くのに 必要な資源の上限を求める研究です。 この議論において計算量を示す方法が重要です。 「手元のパソコンで 4 秒」などという方法では比較の対象になりません。 実際、 OS やハードウェアの評価のためにベンチマークテストと いう特定のプログラムを動作させて実行速度を計測することがよく行われてま す。 これは雑誌によく掲載され、性能を求める利用者にとってよい広告になります。 そこで、良い成績を出そうという企業が、特定のベンチマークテスト を検知し、そのベンチマークテストに対しては処理を行わずに素早く処理を停 止させる 不正な製品を作ることがあります。

一方、特定の入力に対しては if 文であらかじめ計算しておいた値を出力すれ ば、高速に答えを得ることができるので、「ある特定状況下で使用する資源量」 では問題の難しさの本質を議論できません。

そのため、基本的にはプログラムの利用資源量は、入力の長さに関する関数と して与え、関数を比較する必要があります。

但し、さらにプログラムには次のような性質があります。

線形加速定理

ある問題を T(n) 時間で計算できるプログラムがある時、同じ問題を cT(n)+2n 時間で計算できるプログラムを作ることができる(c>0)。

証明のアイディア

一度に処理するビット数を増やすことにより、一度に何ステップ を動作可能になることを示すことです。 但し、詳細な証明はプログラムを実行する枠組に依存するため、省略します。

この定理を使うと、例えば $100n^2+1000n+100$ 秒で計算できる問題は $n^2+12n+1$ 秒で計算できます。 そのため、プログラムの利用資源量を表すには通常オーダという 表現が用いられます。 直感的にはオーダーは関数の項のうち、最も増加の速い項から定数倍を取り除 いたものです。 例えば、次のように表現します。

定義

f(n), g(n) に対して、 f(n)=O(g(n)) とは、ある c が存在して、 十分大きい全ての n に対して、 f(n)≤ c g(n) が成り立つこと。

次にある意味計算量理論の意義を示す定理を紹介します。 これは、時間やメモリがあればあるだけ解決できる問題が増えると言うもので す。

階層定理

$T_1\left(n\right)=O\left(T_2\left(n\right)log\left(T_2\left(n\right)\right)\right)$ を満たす時、どのような T₂(n)時間で計算するプログラムでも計 算できない、T₁(n)時間計算可能な問題が存在する。

例2-2

n 時間で計算できない n²計算可能な問題が存在します。

証明のアイディア

今のところ、T₂(n)時間で計算可能なプログラムに対して、インタ プリタで処理する場合、少なくとも T₂(n)log(T₂(n)) 時間かかります(これより速いものができたら大発見)。 なぜ、 log 分だけ増えるかというと、プログラムが同時にアクセスを要求す るメモリを制限しないため、用意したメモリに適合させるように複数の要求を ひとつの記憶領域にまとめるのに時間がかかります。

証明方法は前回の K と同様です。 求める関数は次のようなものです。

1. 入力 x を Gödel 数と解釈し、プログラムとして扱います。
2. インタプリタにプログラムとして x、入力値として x を入れます。
3. T₂(n)log(T₂(n))ステップだけインタプリタを走 らせ、停止させます。
4. この実行で 1 を出力したら 0、 それ以外(途中で計算を打ち切られた場 合も含む)なら 1 を出力します。

この関数は O(T₂(n)log(T₂(n))) 時間で実行できます ので、条件より T₁(n)時間で実行できます。

一方、T₂(n) 時間実行可能な関数のうち、どのような関数を持っ てきてもこの関数を求めることはできません。 なぜなら、対角線論法により、その関数を計算するプログラムの Gödel 数が y の時、 その関数に y を入れた値は上記の定義により必ず食い違うか らです。

多項式時間還元可能性

polynomial time many-one reducibility $A{\le }_{\text{m}}^{\text{p}}B$ (A が B に多項式時間 many-one reducible)

ある多項式時間計算可能関数 f が存在して、 $x\in A⟺f\left(x\right)\in B$

polynomial time Turing reducibility $A{\le }_{\text{T}}^{\text{p}}B$ (A が B に多項式時間 Turing reducible)

任意の y が B に含まれるかどうかを 1 step で判定するサブルーチンの存在を仮定 すると、入力 x が A に含まれるかどうかを多項式時間で解くプログラムが作 れる。

多項式時間と計算クラス

reducibility は推移律が成り立つ必要があります。 つまり多項式時間 Turing reducibility は以下の関係が成り立つ必要があります。 (many one に書き換えないと linear time が出てこない)

ここで $A{\le }_{\text{T}}^{\text{p}}B$ に $p_1\left(n\right)$ 時間、 $B{\le }_{\text{T}}^{\text{p}}C$ に $p_2\left(n\right)$ 時間かかるとします。 この時、 $A{\le }_{\text{T}}^{\text{p}}C$ にどのくらいの時間がかかるでしょうか？ 入力 x が A に含まれることを調べるのに、y₁, y₂, ..., y_k を B に質問しなければならないとします。 この時、|x| は x の長さを表すとすると k≤p₁(|x|) となりま す。 また、各 y_i の長さは、計算時間が高々 p₁(|x|) し かないので、同様に |y_i|≤p₁(|x|) となります。 ここで、 $B{\le }_{\text{T}}^{\text{p}}C$ を適用すると、各 y_i が B に入るかどうかは C に質問するプロ グラムにより p₂(|y_i|) 時間で計算できます。 従って、 $A{\le }_{\text{T}}^{\text{p}}C$ を計算するのに、次の時間かかります。

階層定理があるので、例えば O(n²) 計算時間の問題や、 O(n³) 計算時間の問題など、実行時間の関数のオーダの違い毎に 区分する考え方は意味があります。

一方、 $A{\le }_{\text{T}}^{\text{p}}B$ に n² 時間かかり、 $B{\le }_{\text{T}}^{\text{p}}C$ に n³ 時間かかるとすると、 $A{\le }_{\text{T}}^{\text{p}}C$ に最悪 n²+n⁶ 時間かかることになります。 これは単純なオーダによる計算時間で区切ったクラスで reducibility を議論 したためです。 これでは、推移律を満たすために合成した関数なりプログラムの計算量が計算時 間を越えてしまいます。 結局これは推移律を満たすために合成した関数の計算量が上記のように関数の和や 合成により得られるためです。

したがって、reducibility を考慮する問題のクラスを定義するには、計算量 を示す関数のオーダーが合成と和について閉じてなければなりません。 そのように閉じている例として次の関数族があります。

1. 線形関数 cn
2. 多項式
3. 対数

線形時間

c₁n 時間と c₂n 時間の reducibility の合成にかか る時間は、最悪でも c₁n + c₂ c₁ n なの で線形時間に収まります。

多項式時間

c₁n^k₁ 時間と c₂n^k₂ 時間の reducibility の合成にかか る時間は、最悪でも c₁n^k₁ + c₂ c₁^k₂ n^k₁k₂ となるので、これも多項式時間。

対数時間

c₁log n 時間と c₂log n 時間の reducibility の合成にかか る時間は、最悪でも c₁log n + c₂log (c₁ log n)。この右側の項は O(log n) より対数時間。

このうち、対数時間は通常の計算モデルでは入力を全て見ることができません。 また、線形時間では行列の計算すらできないので、実用的なプログラムの効率 を考える問題のクラスとしては範囲が狭いです。 そこで、計算量理論で最も重要で基本的なプログラムの効率のクラスは多項式 時間になります。これを Pで表します。

また、多項式領域計算をPSPACE で表します。 多項式時間内には高々多項式領域しか使えないので、 P⊆PSPACE が成り 立ちます。

また、reducibility を多項式時間に限定するとき、 2^cnk 時間もこの reducibility において閉じていま す。 この時間の計算量のクラスを EXPTIME で表します。 階層定理より P⊂EXPTIME が成り立ちます。

一方自明ではありませんが、PSPACE⊆EXPTIME が成り立ちます。 つまり P⊆PSPACE⊆EXPTIME となります。

なお、合成などの議論は全て多項式時間 Turing reducibility で議論しまし たが、多項式時間 many-one reducibility でも同様の議論が成り立ちます。

reducibility に対して安定した問題のクラスを得たところで、完全問題を考 えます。 問題 A が EXPTIME-完全とは、全ての EXPTIME に含まれる問題 B に対して、 $B{\le }_{\text{m}}^{\text{p}}A$ が成り立つことです。 例えば、 n×n の囲碁が先手必勝かどうかを判定するような問題が EXPTIME 完全に含まれます(つまり絶対に多項式時間のような効率の良い計算では解け ないことが言えます)。 なお、19×19 の通常の囲碁の場合、後手は先手に対し、 5.5 目のハンディを もらうのが通常なので、経験的には先手必勝です。