1 第４章 計算の複雑さ入門
第４章 計算の複雑さ入門
4.1. 計算の複雑さの理論概観
「計算可能か？」Î「どの程度の計算コストで計算可能か？」
計算の複雑さの理論(Computational Complexity Theory) (1) 計算量の上限に関する研究
(2) 計算量の下限に関する研究 (3) 計算の難しさについての構造的研究
(1)計算量の上限に関する研究
効率のよいアルゴリズムの設計（アルゴリズム理論）
ある問題Xに対して，それを解くアルゴリズムA があり，
サイズn のどんな問題例に対してもA の時間計算量が
T(n) 以内であるとき，アルゴリズムA の時間計算量の
上限はT(n)
（最悪時の漸近的時間計算量）
1/14
(2) 計算量の下限に関する研究
問題X に対するどんなアルゴリズムも最悪の場合にはT(n)
時間だけ必ずかかってしまうとき，問題Xの時間計算量の 下限はT(n).
・P NP予想
・暗号システムの頑健さ (3) 計算の難しさについての構造的研究
“xx程度の難しさ”がもつ特徴について調べること．
難しさの程度による階層構造．
≠
2/14
4.2. 計算時間の計り方 4.2.1. 標準形プログラム再考 定義4.1. （計算時間の定義）
A: k入力標準形プログラム x1, x2, ..., xk: Aへの入力
Aのwhileループ１回り分の実行をAでの１ステップという．
入力x1, x2, ..., xkに対してAが停止するまでに回るwhileループの
回数をAのx1, x2, ..., xkに対する計算時間（略してA(x1, x2, ..., xk) の計算時間）という．ただし，停止しないとき，計算時間は無限大．
time_A(x1, x2, ..., xk) A(x≡ 1, x2, ..., xk)の計算時間
3/14
•全体はwhile ループ
•各行は
¾1つのif 文+pcへの代入
¾基本命令1つ+pcへの代入
1 2
1
_ ( ) max{ _ ( , ,..., k) : | i| }
i k
time A l time A x x x x l
≤ ≤
∑
=標準形プログラム progプログラム名(input ...);
var pc: Σ∗; ... ; Σ; ... ; Σ∗;
begin pc:=1;
while pc 0 do case pc of 1: （文）;
2: （文）;
3: （文）;
...
K: （文）;
end-case end-while;
halt(Σ∗型の変数）;
end.
- if 比較文 then pc:=k1else pc:=k2end-if -代入文; pc:=k;
≠
4/14
各（文）の形は
のいずれか．
・各文が高々定数時間で実行できるための制約 u, u’: Σ型の変数， v, v’: Σ∗型の変数
c: Σ型の定数， s: Σ∗型の定数
（代入文）(1) u := c; (2) u := u’;
(3) u := head(v); (4) u := tail(v);
(5) v := s; (6) v := v’;
(7) v := right(v); (8) v := left(v);
(9) v := u# v; (10) v := v # u;
（比較文）(11) u = c (12) v = s
・v = v’の形の比較は禁止されている．
5/14
??
4.2.2. プログラムの時間計算量
プログラムの時間計算量を入力サイズの関数として表現
（入力文字列の長さ）
妥当なコード化：
元の対象のサイズに定数倍の範囲内で忠実なコード化 例4.5: 1進表記と2進表記
「数のサイズはその桁数」との立場では 2進表記は妥当なコード化であるが，
1進表記は冗長なコード化
6/14
2
定義4.3: 自然数上の関数f, gに対し，
ヨc,d>0, ∀n[f(n)≦c g(n) + d]
となるとき，f はオーダーgであるといい，f =O(g) と記述する．
定理4.1:自然数上の任意の関数f, g, h に対し次の関係が成立。
(1)∀n[f(n) ≦g(n)] Æf = O(g) (2)ヨc > 0, n[f(n)≦cg(n)] Æf = O(g) (3) [ f = O(g) かつg = O(h)] Æf = O(h)
∀∞
★定数c, dはnと無関係に定まることが必要．
7/14
4.2.3. 問題の時間計算量
定義4.4.Φ を計算問題とし，tを自然数上の関数とする．
いまΦ を計算するプログラムA と定数c, d >0が存在して，
∀l[time_A(l) ≦ct(l) + d]
ならば，ΦはO(t)時間計算可能，あるいはΦの時間計算量は
O(t)であるという．
注意：ここでは計算問題として，集合の認識問題を想定している．
直観的には「問題Φはt時間以下で計算可能」という意味。
(注1) A の時間計算量はt より低いかもしれない．
(注2) A よりも速くΦを計算するプログラムがあるかもしれない．
8/14
例4.7. 素数判定問題の時間計算量 素数判定問題(PRIME) 入力：自然数n（ただし，2進表記）
質問：n は素数か？
PRIME { : nは素数}≡ ⎡ ⎤n prog Naive(input n);
begin
for each i := 1 < i < n do if n mod i = 0 then reject end-if end-for;
accept end.
log n・log i 時間
2 ～n-1の数で割ってみる
n の長さをl とすると，l はほぼlog nだから，time_Naive=O(l22l) 故に，素数判定問題の時間計算量は（高々）O(l22l)
9/14
) log log ( ) ( Naive
_ n 1 c n i d
time ≤
∑
<i<n + ) ) (log (! log
logn n dn On n2
c + =
=
余談：
2002年に のアルゴリズム が考案された!!
) (l6 O スターリングの公式：
n
e n n
n ⎟
⎠
⎜ ⎞
⎝
≈ 2π⎛
!
定義4.5.
自然数上の関数tに対し，時間計算量がO(t) となる集合
（i.e.,認識問題）の全体をO(t) 時間計算量クラスといい，
そのクラスをTIME(t)と表す．
また，tのような関数を制限時間と呼ぶ．
たとえば，O(l22l) 時間で認識可能な集合を集めたクラスが
TIME(l22l)であり，集合PRIME はその一要素．
PRIME TIME(l∈ 22l)
10/14
今ではPRIME ∈TIME (l6)
l l2
l6 2l l22l
×
×
多項式 指数関数
制限時間t にふさわしい関数の条件
(a) n[ n t(n) ]
(b) n１, n2[n1< n2Æt(n1) t(n2)]
(c)与えられた入力x に対し，t(|x|)（t(|x|)の1進表記）を 求める計算がO(t) 時間で可能
(a)の条件：入力を読むだけでn 時間かかってしまうから．
(c)の条件：時間がt(n) になったら計算を打ち切るようにするため
のタイマーが実現できるようにするため．
（1進表記を作って，1桁ずつ短くしていく）．
∀∞
∀∞ ≤
≤
11/14
自然な制限時間(の定義)
例4.8: 集合D = {<a,b>: aはbで割り切れる}の時間計算量 集合Dを認識するプログラムとして，下のプログラムを考える．
prog D(input x);
begin
a:=get(x, 1); b:=get(x, 2);
% x= <a,b>の形でないときは，この時点でreject if a mod b= 0 then accept else reject end-if
end. O(|a||b|)時間で計算可能
time_D(x) = O(|x|2)
入力がx=<a,b>の形のときはO(|x|2)時間かかるが，そうでない 場合にはmod計算の前にrejectするので，O(|x|)時間で終って しまう．これは自然な制限時間の条件(b) に反するが，
Dの最悪時の効率を議論するには，制限時間としてn2を使い，
time_D(l) = O(l2)と評価しても十分である．
12/14
3
例4.9. 制限時間n2 が条件(c)を満たすこと 入力列xÎO(|x|2)時間以内で出力0|x|2を出力．
以下に基本的なアイディアを示す（プログラムsq) w1:=x # 0; y:= ε; xは入力変数，yは出力変数 while w1 εdo
w1:=right(w1); w2:=x;
while w2 εdo このループで w2:=right(w2); y:=y # 0; |y| Å|y|+|x|となる end-while
end-while;
≠
≠
入力の長さをlとすると，
内側のwhileループはl回 （1回あたり3ステップ）
外側のwhileループはl+1回 全体で 2+(l+1)(3+3l) = 3l2+ 6l+ 5
time_sq(l) = O(l2)
13/14
定理4.2:関数t1, t2を任意の自然な制限時間とする．このとき，
t1+ t2, t1×t2, t1o t2も自然な制限時間．
定理4.3: すべての制限時間t1, t2に対し，
t1=O( t2) ÆTIME(t1) TIME( t2).
証明：
すべてのLで，L∈TIME(t1) ÆL∈TIME(t2)を示せばよい．
定義より，LをO(t1)で認識するプログラムAが存在．
つまり，time_A = O(t1).
t1=O(t2)だから，
time_A = O(t2).
よって，Lの時間計算量はO(t2)．
すなわち，L∈TIME(t2) . 証明終 14/14
⊆
