計算困難問題に対するアルゴリズム理論

study book draft 2021-12-20 Author: J.ホロムコヴィッチ Title: 計算困難問題に対するアルゴリズム理論

2.3 アルゴリズム論の基礎

2.3.1 アルファベット,語,言語

定義 2.3.1.1 任意の空ではない有限集合をアルファベットと呼ぶ.アルファベット $Σ$ の任意の集合は $Σ$ のシンボルと呼ばれる.

アルファベットの例としては

$Σ_{b oo l} = {0, 1},$ $Σ_{l a t} = {a, b, c, ..., z},$ $Σ_{l o g i c} = {0, 1, (,), \land, \lor, \neg, x}$ などがある.

定義 2.3.1.2 $Σ$ をアルファベットとする. $Σ$ 上の語は， $Σ$ のシンボルの任意の有限列である.空語 $λ$ は0個のシンボルからなる唯一の語である.アルファベット $Σ$ 上のすべての語の集合を $Σ^{*}$ で表す.

定義 2.3.1.3 アルファベット $Σ$ 上の語 $w$ の長さは $∣ w ∣$ と表され， $w$ に含まれるシンボルの数（すなわち，列としての $w$ の長さ）である.任意の語 $w \in Σ^{*}$ と任意のシンボル $a \in Σ$ に対して, $#_{a} (w)$ は語 $w$ に現れるシンボル $a$ の数を表す.

語 $w = 010010$ に対して， $∣ w ∣ = 6$ , $#_{0} (w) = 4$ , $#_{1} (w) = 2$ .任意のアルファベット $Σ$ と任意の語 $w \in Σ^{*}$ に対して， $∣ w ∣ = Σ_{a \in Σ} #_{a} (w)$

2.3.2 アルゴリズム問題

Aをアルゴリズムとし，xを入力するとき， $A (x)$ は入力xに対するAの出力を表す.

定義 2.3.2.1　決定問題は，3項組 $(L, U, Σ)$ である.ここで， $Σ$ はアルファベットで $L \subseteq U \subseteq Σ^{*}$ である.アルゴリズムAが決定問題 $(L, U, Σ)$ を解く（決定する）というのは，任意の $x \in U$ に対して，

(i) $x \in L$ の時, $A (x) = 1$ , (ii) $x \in U - L (x \in / L)$ の時, $A (x) = 0$ となることである. この定義は次の入出力の振る舞いを指定する形式と等価である.

問題 $(L, U, Σ)$ 入力： $x \in U$ 出力： $x \in L$ なら「はい」,そうでなければ「いいえ」.

多くの決定問題 $(L, U, Σ)$ に対しては $U = Σ^{*}$ を仮定している．その場合 $(L, Σ^{*}, Σ)$ の代わりに略記法 $(L, Σ)$ を用いる．

定義 2.3.2.2 最適化問題は以下の条件を満たす７項組 $U = (Σ_{I}, Σ_{O}, L, L_{I}, M, cos t, g o a l)$ で定義される． (i) $Σ_{I}$ はアルファベットで， $U$ の入力アルファベットと呼ばれる． (ii) $Σ_{O}$ はアルファベットで， $U$ の出力アルファベットと呼ばれる． (iii) $L (\subseteq Σ_{I}^{*})$ は実行可能な問題インスタンスの言語． (iv) $L_{I} \subseteq L$ は $U$ の（実）問題インスタンスの言語． (v) $M$ は $L$ から $P o t (Σ_{O}^{*})$ への関数で，任意の $x \in L$ に対して， $M (x)$ は $x$ に対する実行可能解の集合と呼ばれる． (vi) $cos t$ は任意の対 $(u, x)$ に対するコスト関数である．ここで， $u \in M (x)$ であり，ある $x \in L$ に対して，正の実数 $cos t (u, x)$ を割り当てる． (vii) $g o a l \in {minim u m, ma x im u m}$ ．

任意の $x \in L_{I}$ に対して， $cos t (y, x) = g o a l {cos t (z, x) ∣ z \in M (x)}$ の時，実行可能解 $y \in M (x)$ は $x$ と $U$ に対して最適であるという．ある最適解 $y \in M (x)$ に対して， $cos t (x, y)$ を $Op t_{U} (x)$ によって表す． $g o a l = minim u m$ の時， $U$ を最小化問題と呼ぶ．以下では， $U$ のインスタンス $x$ に対する全ての最適解の集合を $O u tp u t_{U} (x) \subseteq M (x)$ で表す．アルゴリズム $A$ が，任意の $x \in L_{I}$ に対して $A (x) \in M (x)$ を出力する時， $U$ に対して無矛盾であるという．アルゴリズム $B$ に対して，以下を満たす時， $B$ は最適化問題 $U$ を解くという． (i) $B$ が $U$ に対して無矛盾である． (ii) 任意の $x \in L_{I}$ に対して， $B (x)$ が $x$ と $U$ に関して最適解である．

2.3.3 計算量理論

一様コスト尺度
- 時間計算量の測定は，考えている計算において実行される初等的命令の全体数を決定することからなる．
- 空間計算量の測定は，計算中に使用された変数の数を決定することからなる．
  - 利点：コストの測定が単純である
  - 欠点：全ての演算についてコスト１を考えるので，いつも適当であるとは限らない
- 全体の計算中に全ての変数のサイズがある程度固定された定数（想定される計算機の語長）で抑えられる値だけを含むことが仮定できる場合にのみ適用し得る．
対数コスト尺度
- 任意の初等演算のコストは被演算数に対する２進表現のサイズの和
- 通常，これがアルゴリズムの計算量解析に採用されている
- nビット整数の乗算に対する最良のアルゴリズムは $Ω (n \cdot lo g n)$ の2進演算を必要とするので，乗算と除算の計算量は $O (n \cdot lo g n)$ と考える．

定義 2.3.3.1 $Σ_{I}$ と $Σ_{O}$ をアルファベットとする． $A$ を $Σ_{I}^{*}$ から $Σ_{O}^{*}$ への写像を実現するアルゴリズムとする．任意の $x \in Σ_{I}^{*}$ に対して， $T im e_{A} (x)$ を（対数コストに関する）入力 $x$ における $A$ の計算に対する時間計算量を表し， $Sp a c e_{A} (x)$ を（対数コストに関する）入力 $x$ における $A$ の計算に対する空間計算量を表す．

定義 2.3.3.2 $Σ_{I}$ と $Σ_{O}$ を２つのアルファベットとする． $A$ を $Σ_{I}^{*}$ から $Σ_{O}^{*}$ への写像を計算するアルゴリズムとする． $A$ の（最悪）計算量は，任意の正整数 $n$ に対して $T im e_{A} (n) = max {T im e_{A} (x) ∣ x \in Σ_{I}^{n}}$ と定義される関数 $T im e_{A} : (N - {0}) \to N$ である． $A$ の（最悪）計算量は $Sp a c e_{A} (n) = max {Sp a c e_{A} (x) ∣ x \in Σ_{I}^{n}}$ によって定義される関数 $Sp a c e_{A} : (N - {0}) \to N$ である．

この計算量解析の定義は最悪時解析と呼ばれる
- $T im e_{A}$ をこのように定義すると，サイズ $n$ の任意の入力（すなわち， $Σ_{I}^{*}$ の任意の入力）は $A$ によって高々 $T im e_{A} (n)$ 時間で解くことができ， $T im e_{A} (x) = T im e_{A} (n)$ となるサイズ $n$ の入力 $x$ が存在するため
欠点：同じ長さの入力に対して非常に異なる計算量を持つアルゴリズムのときにうまく計算量を計量できない
- 平均計算量を用いる
  - 平均計算量を決定することは $T im e_{A} (n)$ を決めることよりもずっと難しい
  - 任意の固定長の入力における現実的な確率分布上で平均が取られているときのみ，平均情報量が有用
数論においては，入力サイズを厳密に入力の2進表現の長さとして考える

定義 2.3.3.4 $U$ を問題とし， $f$ と $g$ を $N$ から $R^{+}$ への関数とする． $U$ ｑを $T im e_{A} (n) \in O (g (n))$ で解くアルゴリズム $A$ が存在する時， $O (g (n))$ は $U$ の時間計算量の上界であるという． $U$ を解く任意のアルゴリズム $B$ が $T im e_{B} (n) \in Ω (f (n))$ となるならば， $Ω (f (n))$ は $U$ の時間計算量の下界であるという． $T im e_{C} (n) \in O (g (n))$ が成り立ち， $Ω (g (n))$ が $U$ の時間計算量の下界である時，アルゴリズム $C$ は問題 $U$ に対して最適であるという．

任意のTM(アルゴリズム)Mに対して， $L (M)$ はMによって決定される言語を表すとする．

定義 2.3.3.5 多項式時間で決定可能な言語のクラスPを $P = {L = L (M) ∣ M$ はある正整数 $c$ に対して， $T im e_{M} (n) \in O (n^{c})$ 時間のTM(アルゴリズム）である $}$

Bantako's notes garden

エクスプローラー

計算困難問題に対するアルゴリズム理論

2.3 アルゴリズム論の基礎

2.3.1 アルファベット,語,言語

2.3.2 アルゴリズム問題

2.3.3 計算量理論

グラフビュー

目次