ブルームの公理

計算複雑性理論において、ブルーム公理またはブルーム複雑性公理は、計算可能関数 の集合における複雑性尺度の望ましい特性を指定する公理である。この公理は1967年にマヌエル・ブルームによって初めて定義された。 ^[1]

重要なのは、Blum のスピードアップ定理とギャップ定理は、これらの公理を満たすあらゆる複雑性尺度に当てはまるということです。これらの公理を満たす最もよく知られた尺度は、時間 (つまり、実行時間) と空間 (つまり、メモリ使用量) の尺度です。

ブルーム複雑度尺度は、部分計算可能関数の番号と計算可能関数 のペアである。${\displaystyle (\varphi ,\Phi )}$${\displaystyle \varphi}$ ${\displaystyle \mathbf {P} ^{(1)}}$

${\displaystyle \Phi :\mathbb {N} \to \mathbf {P} ^{(1)}}$

これは次のブルーム公理を満たします。ゲーデル番号付けの下でi番目の部分計算可能関数を と書き、部分計算可能関数を と書きます。 ${\displaystyle \varphi_{i}}$${\displaystyle \varphi}$${\displaystyle \Phi_{i}}$${\displaystyle \Phi (i)}$

• とのドメインは同一です。${\displaystyle \varphi_{i}}$${\displaystyle \Phi_{i}}$
• 集合は再帰的です。${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}}$

• ${\displaystyle (\varphi ,\Phi )}$は、 iによってコード化された計算に必要な時間またはメモリ（あるいはそれらの適切な組み合わせ）である場合に、複雑さの尺度となります。${\displaystyle \Phi}$
• ${\displaystyle (\varphi ,\varphi )}$2 番目の公理を満たしていないため、複雑性の尺度ではありません。

計算可能関数全体 の計算複雑性クラスは次のように定義できる。 ${\displaystyle 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)}$