ブラムの公理

計算複雑性理論におけるブラムの公理（ブラムのこうり、英: Blum axioms）またはブラムの複雑性公理とは、計算可能関数の集合上の複雑性測度の満たすべき性質を述べた公理である。この公理はマヌエル・ブラムによって1967年に導入された。^[1]

重要な結果として、公理を満たす任意の複雑性測度でブラムの加速定理とギャップ定理が成り立つことが知られる。公理を満たす測度として最もよく知られているものとしては時間複雑性と空間複雑性がある。

定義

ブラム複雑性測度（英: Blum complexity measure）とは、1変数部分計算可能関数のアクセプタブル・ナンバリング ${\displaystyle \varphi }$ と、計算可能関数

${\displaystyle \Phi :\mathbb {N} ^{2}\to \mathbb {N} }$

の組 ${\displaystyle (\varphi ,\Phi )}$ で、次のブラムの公理を満たすものをいう。

• ${\displaystyle \varphi _{i}}$ の定義域と ${\displaystyle \Phi _{i}}$ の定義域は等しい
• 集合 ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}}$ は計算可能である

例

${\displaystyle \varphi }$ を適当な計算模型から得られたacceptableナンバリングとする。${\displaystyle \Phi }$ を時間または空間 (もしくはそれらを適当に組合せた) 複雑性とすれば、${\displaystyle (\varphi ,\Phi )}$ は複雑性測度である。時間量や計算量は実際に計算を走らせてみれば分かるから計算可能である。${\displaystyle \Phi }$ が時間量のとき ${\displaystyle \Phi _{e}(x)=t}$ であるか否かは計算を ${\displaystyle t}$ 時間だけ走らせてみれば分かるから計算可能である。${\displaystyle \Phi }$ が空間量のときに2番目の公理を満たすことは考察を必要とする。それには空間量を ${\displaystyle t}$ 以下に制限したとき系が取りうる状態数が有限であることに注意すればよい。例えば状態記号の数が ${\displaystyle q}$ でテープ記号の数 ${\displaystyle s}$ のチューリング機械を考えると、テープ状態の総数は ${\displaystyle s^{t}}$ でありヘッド位置の総数は ${\displaystyle t}$ であるから、系全体の取りうる状態の数は高々 ${\displaystyle qs^{t}t}$ である。したがって計算を十分な時間だけ走らせれば、計算が終了するか、ある状態が繰り返し現れて無限ループに陥るか、または空間量の制限を超過するかの何れかが起こる。その何れであるかは実効的に判定できるから、したがって ${\displaystyle \Phi _{e}(x)=t}$ であるか否かは計算可能である。

${\displaystyle (\varphi ,\varphi )}$ は2番目の公理を満たさないから複雑性測度ではない。

模型に対する独立性

ブラム複雑性測度は特定の計算模型によらず定義されている。もっと分かりやすくする為に、ブラムの公理をチューリング機械の言葉で次のように言い換えることもできる。

ブラム複雑性測度とは、順序対 (チューリング機械 ${\displaystyle M}$, 入力 ${\displaystyle x}$) から自然数または ${\displaystyle \infty }$ への写像であって、次の公理を満たすものをいう：

• ${\displaystyle \Phi (M,x)}$ が無限大でないとき、かつそのときに限り ${\displaystyle M(x)}$ は停止する
• 入力 ${\displaystyle (M,x,n)}$ が ${\displaystyle \Phi (M,x)=n}$ を満たすかどうか決定するアルゴリズムが存在する

例えば、${\displaystyle \Phi (M,x)}$ を M に x を入力して実行してから停止するまでに要するステップ数とする。1番目の公理は明らか。2番目の公理は、万能チューリング機械に M と x を入力して n ステップ目までの計算を模倣すれば判定できるからよい。

複雑性クラス

全域計算可能関数 ${\displaystyle f}$ に対して複雑性クラス ${\displaystyle C(f)}$ と ${\displaystyle C^{0}(f)}$ が次のように定義される

${\displaystyle C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\}}$

${\displaystyle C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}}$

${\displaystyle C(f)}$ は複雑性が ${\displaystyle f}$ 以下である全ての計算可能関数からなる集合である。${\displaystyle C^{0}(f)}$ は複雑性が ${\displaystyle f}$ 以下である全てのブール値関数からなる集合である。もしこれらの関数を集合の指示関数と見做すならば、${\displaystyle C^{0}(f)}$ は集合の複雑性クラスと考えられる。

関連項目

• 計算複雑性理論

参考文献