ブラムの公理のソースを表示

[[計算複雑性理論]]における'''ブラムの公理'''（ブラムのこうり、{{lang-en-short|Blum axioms}}）または'''ブラムの複雑性公理'''とは、[[計算可能関数]]の集合上の複雑性測度の満たすべき性質を述べた公理である。この公理は[[マヌエル・ブラム]]によって1967年に導入された。<ref>{{cite journal|last1=Blum|first1=Manuel|title=A Machine-Independent Theory of the Complexity of Recursive Functions|journal=Journal of the ACM|volume=14|issue=2|year=1967|pages=322–336|issn=00045411|doi=10.1145/321386.321395}}</ref>

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

== 定義 ==

'''ブラム複雑性測度'''（{{lang-en-short|Blum complexity measure}}）とは、1変数[[計算可能関数|部分計算可能関数]]の[[ナンバリング_(計算可能性理論)|アクセプタブル・ナンバリング]] <math>\varphi</math> と、計算可能関数
:<math>\Phi: \mathbb{N}^{2} \to \mathbb{N} </math>
の組 <math>(\varphi, \Phi)</math> で、次の'''ブラムの公理'''を満たすものをいう。
* <math>\varphi_i</math> の[[定義域]]と <math>\Phi_i</math> の定義域は等しい
* 集合 <math>\{(i,x,t) \in \mathbb{N}^3 | \Phi_i(x) = t\}</math> は計算可能である

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

<math>(\varphi, \varphi)</math> は2番目の公理を満たさないから複雑性測度ではない。

== 模型に対する独立性 ==

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

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

* <math>\Phi(M,x)</math> が無限大でないとき、かつそのときに限り <math>M(x)</math> は[[停止問題|停止]]する
* 入力 <math>(M,x,n)</math> が <math>\Phi(M,x)=n</math> を満たすかどうか決定するアルゴリズムが存在する

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

== 複雑性クラス ==

[[計算可能関数|全域計算可能関数]] <math>f</math> に対して[[複雑性クラス]] <math> C(f)</math> と <math> C^0(f) </math> が次のように定義される
:<math>C(f) := \{ \varphi_i \in \mathbf{P}^{(1)} | \forall x.\ \Phi_i(x) \leq f(x) \}</math>
:<math>C^0(f) := \{ h \in C(f) | \mathrm{codom}(h) \subseteq \{0,1\} \}</math>

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

== 関連項目 ==
* [[計算複雑性理論]]

== 参考文献 ==

{{Reflist}}
{{デフォルトソート:ふらむのこうり}}
[[Category:計算複雑性理論]]
[[Category:公理]]
[[Category:数学に関する記事]]