ブラムの公理

計算複雑性理論におけるブラムの公理（ブラムのこうり、）またはブラムの複雑性公理とは、計算可能関数の集合上の複雑性測度の満たすべき性質を述べた公理である。この公理はマヌエル・ブラムによって1967年に導入された。
重要な結果として、公理を満たす任意の複雑性測度でブラムの加速定理とギャップ定理が成り立つことが知られる。公理を満たす測度として最もよく知られているものとしては時間複雑性と空間複雑性がある。
定義.
ブラム複雑性測度（）とは、1変数部分計算可能関数のアクセプタブル・ナンバリング formula_1 と、計算可能関数
の組 formula_3 で、次のブラムの公理を満たすものをいう。
例.
formula_1 を適当な計算模型から得られたacceptableナンバリングとする。formula_8 を時間または空間 (もしくはそれらを適当に組合せた) 複雑性とすれば、formula_3 は複雑性測度である。時間量や計算量は実際に計算を走らせてみれば分かるから計算可能である。formula_8 が時間量のとき formula_11 であるか否かは計算を formula_12 時間だけ走らせてみれば分かるから計算可能である。formula_8 が空間量のときに2番目の公理を満たすことは考察を必要とする。それには空間量を formula_12 以下に制限したとき系が取りうる状態数が有限であることに注意すればよい。例えば状態記号の数が formula_15 でテープ記号の数 formula_16 のチューリング機械を考えると、テープ状態の総数は formula_17 でありヘッド位置の総数は formula_12 であるから、系全体の取りうる状態の数は高々 formula_19 である。したがって計算を十分な時間だけ走らせれば、計算が終了するか、ある状態が繰り返し現れて無限ループに陥るか、または空間量の制限を超過するかの何れかが起こる。その何れであるかは実効的に判定できるから、したがって formula_11 であるか否かは計算可能である。
formula_21 は2番目の公理を満たさないから複雑性測度ではない。
模型に対する独立性.
ブラム複雑性測度は特定の計算模型によらず定義されている。もっと分かりやすくする為に、ブラムの公理をチューリング機械の言葉で次のように言い換えることもできる。
ブラム複雑性測度とは、順序対 (チューリング機械 formula_22, 入力 formula_23) から自然数または formula_24 への写像であって、次の公理を満たすものをいう：
例えば、formula_25 を "M" に "x" を入力して実行してから停止するまでに要するステップ数とする。1番目の公理は明らか。2番目の公理は、万能チューリング機械に "M" と "x" を入力して "n" ステップ目までの計算を模倣すれば判定できるからよい。
複雑性クラス.
全域計算可能関数 formula_30 に対して複雑性クラス formula_31 と formula_32 が次のように定義される
formula_35 は複雑性が formula_30 以下である全ての計算可能関数からなる集合である。formula_37 は複雑性が formula_30 以下である全てのブール値関数からなる集合である。もしこれらの関数を集合の指示関数と見做すならば、formula_37 は集合の複雑性クラスと考えられる。