ブラムの公理
全域計算可能関数 f {\displaystyle f} に対して複雑性クラス C ( f ) {\displaystyle C(f)} と C 0 ( f ) {\displaystyle C^{0}(f)} が次のように定義される
C ( f ) := { φ i ∈ P ( 1 ) | ∀ x . Φ i ( x ) ≤ f ( x ) } {\displaystyle C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\}}
C 0 ( f ) := { h ∈ C ( f ) | c o d o m ( h ) ⊆ { 0 , 1 } } {\displaystyle C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}}
C ( f ) {\displaystyle C(f)} は複雑性が f {\displaystyle f} 以下である全ての計算可能関数からなる集合である。 C 0 ( f ) {\displaystyle C^{0}(f)} は複雑性が f {\displaystyle f} 以下である全てのブール値関数からなる集合である。もしこれらの関数を集合の指示関数と見做すならば、 C 0 ( f ) {\displaystyle C^{0}(f)} は集合の複雑性クラスと考えられる。