ブルーム公理

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

重要なのは、ブルームの高速化定理とギャップ定理は、これらの公理を満たす任意の複雑性尺度に対して成立することです。これらの公理を満たす最もよく知られた尺度は、時間（すなわち実行時間）と空間（すなわちメモリ使用量）です。

意味

まず、すべての部分計算可能関数を列挙する。つまり、これらの関数に計算可能な番号を割り当てる。例えば、特定のプログラミング言語を指定し、それに基づいて辞書式順序でn番目に構文的に有効なプログラムを に割り当てる。2つのプログラムが全く同じ部分関数を計算しても、番号が異なる場合があります。これにより、それぞれの「複雑さ」を区別することができます。 ${\displaystyle \varphi _{0},\varphi _{1},\dots }$ ${\displaystyle \varphi _{n}}$ ${\displaystyle \varphi _{n},\varphi _{m}}$

抽象的に言えば、プログラムの「複雑さ」を測定するということは、任意のプログラム入力 に対して、その入力に対する計算の複雑さ／コストがとなるような関数 を見つけることを意味します。プログラムがで停止しない場合、 は未定義である必要があります。そうでない場合、 は明確な自然数である必要があります。これにより、最初の公理が得られます。 ${\displaystyle \varphi _{n}}$ ${\displaystyle \Phi _{n}}$ ${\displaystyle x}$ ${\displaystyle \varphi _{n}}$ ${\displaystyle \Phi _{n}(x)}$ ${\displaystyle \varphi _{n}}$ ${\displaystyle x}$ ${\displaystyle \Phi _{n}(x)}$ ${\displaystyle \Phi _{n}(x)}$

• とのドメインは同一です。${\displaystyle \varphi _{i}}$ ${\displaystyle \Phi _{i}}$

さらに、計算可能でない複雑性尺度は実用上は興味深くないため、ある意味で計算可能であるべきである。このことから第二の公理が得られる。

• 任意の が与えられたときに が成り立つかどうかを判定するプログラムがあります。が定義されていない場合、定義によりすべての に対して が偽となることに注意してください。つまり、集合は再帰的です。${\displaystyle i,x,c\in \mathbb {N} }$ ${\displaystyle \Phi _{i}(x)\leq c}$ ${\displaystyle \Phi _{i}(x)}$ ${\displaystyle \Phi _{i}(x)\leq c}$ ${\displaystyle c\in \mathbb {N} }$ ${\displaystyle \{(i,x,c)\in \mathbb {N} ^{3}|\Phi _{i}(x)=c\}}$

これらはブルーム公理です。ブルーム複雑度尺度は、ブルーム公理を満たす 組み合わせです。${\displaystyle (\varphi ,\Phi )}$

ブルーム複雑度測度と任意の計算可能関数 が与えられたとき、を で囲まれた複雑度クラスの関数のクラスと定義します。つまり、 は計算可能関数 から構成され、 が存在するような関数が存在します。 ${\displaystyle f}$ ${\displaystyle C[f]}$ ${\displaystyle f}$ ${\displaystyle C[f]}$ ${\displaystyle \phi }$ ${\displaystyle \varphi _{n}}$ ${\displaystyle \forall x,\;\Phi _{n}(x)\leq f(x)}$

計算量クラスの定義は、ほぼすべての入力に対して によって有界となる関数のクラスと緩和されることがあります。つまり、 は計算可能関数 の全体から成り、有限個を除くすべての に対してとなる が存在するということです。 ${\displaystyle {\bar {C}}[f]}$ ${\displaystyle f}$ ${\displaystyle {\bar {C}}[f]}$ ${\displaystyle \phi }$ ${\displaystyle \varphi _{n}}$ ${\displaystyle \Phi _{n}(x)\leq f(x)}$ ${\displaystyle x}$

例

時間計算量はブルーム計算量の尺度です。 かどうかを判断するには、ステップをシミュレートします。ステップが完了する前にマシンが停止した場合はTRUE を出力し、そうでない場合は FALSE を出力します。 ${\displaystyle \Phi _{i}(x)\leq c}$ ${\displaystyle \varphi _{i}(x)}$ ${\displaystyle c}$ ${\displaystyle c}$

同様に、空間の複雑さ、またはそれらの計算可能な組み合わせは、Blum の複雑さの尺度です。

${\displaystyle (\varphi ,\varphi )}$ 2 番目の公理を満たしていないため、複雑性の尺度では ありません。

プロパティ

すべてのステートメントは、「任意の Blum 複雑性尺度について...」で始まることを前提としています。 ${\displaystyle (\varphi ,\Phi )}$

任意の関数を計算するのに、任意の困難な方法があります。 が計算可能な全、および任意の部分計算可能な に対して、となるようなものが存在し、任意の に対して、が定義されている場合、 となります。^{[2] : Thm. 3.18}${\displaystyle f}$ ${\displaystyle \phi }$ ${\displaystyle \varphi _{n}}$ ${\displaystyle \phi =\varphi _{n}}$ ${\displaystyle x}$ ${\displaystyle \varphi _{n}(x)}$ ${\displaystyle \Phi _{n}(x)>h(x)}$

計算量クラスが任意に高い関数が存在する: 任意の全計算可能関数に対して、全計算可能関数は に含まれない。^{[2] : Thm. 3.20}${\displaystyle f}$ ${\displaystyle {\bar {C}}[f]}$

ブルームのスピードアップ定理。

ギャップ定理: 任意の全計算可能関数が与えられた場合、となる全計算可能関数が存在する。 ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle C[f]=C[g\circ f]}$

構成は構成的である。つまり、定理の証明は、 を計算するプログラムが与えられたときに、 を計算するプログラムを出力するという単純なプログラムである。^{[2] : Thm. 3.26}${\displaystyle f}$ ${\displaystyle g}$

McCreightとMeyerの和定理：^[3]を全計算可能関数とし、任意の に対して、有限個を除くすべての に対してとなるものとする。すると、全計算可能関数が存在し、となる。 ${\displaystyle f(n,x)}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle f(n+1,x)>f(n,x)}$ ${\displaystyle x}$ ${\displaystyle F}$ ${\displaystyle C[F]=\cup _{n\in \mathbb {N} }C[f(n,\cdot )]}$

圧縮定理: ^{[2] : Thm. 3.28}を全計算可能関数とする。任意 の に対して、以下の条件を満たす全計算可能関数が存在する。${\displaystyle g(x,n)}$ ${\displaystyle f}$ ${\displaystyle n\in \mathbb {N} }$

• が定義されている場合、 となります。この条件は、出力サイズに複雑さが積み重なるのを避けるために使用されます。${\displaystyle \varphi _{n}(x)}$ ${\displaystyle \varphi _{f(n)}(x)<x}$
• となるような任意のプログラムについて、ほぼすべての に対してが成り立ちます。これにより普遍的な下限が得られます。${\displaystyle m}$ ${\displaystyle \varphi _{m}=\varphi _{f(n)}}$ ${\displaystyle \Phi _{m}(x)\geq \Phi _{n}(x)}$ ${\displaystyle x}$
• ${\displaystyle \Phi _{f(n)}(x)\leq g(x,\Phi _{n}(x))}$ ほぼすべての に対して となる。これにより、存在論的上限が得られる。${\displaystyle x}$

複雑度クラス

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

参考文献

1. Blum, Manuel (1967). 「機械に依存しない再帰関数の計算量理論」(PDF) . Journal of the ACM . 14 (2): 322– 336. doi :10.1145/321386.321395. S2CID  15710280.
2. Smith, Carl H. (1994)、「抽象複雑性理論」、計算理論への再帰的入門、ニューヨーク、NY：Springer New York、pp.  68– 90、doi：10.1007/978-1-4419-8501-9_4、ISBN 978-1-4612-6420-0
3. McCreight, EM; Meyer, AR (1969-05-05). 「計算上の境界によって定義される計算可能関数のクラス：予備報告」 .第1回ACM計算理論シンポジウム議事録. STOC '69. ニューヨーク州ニューヨーク: Association for Computing Machinery: 79–88 . doi :10.1145/800169.805423. ISBN 978-1-4503-7478-1。

• Boas、Peter van Emde (1975)、Bečvář、Jíří (編)、「Ten years of Speedup」、コンピュータ サイエンスの数学的基礎 1975 第 4 回シンポジウム、マリアンスケー ラズニェ、1975 年 9 月 1 ～ 5 日、vol. 32、ベルリン、ハイデルベルク：シュプリンガー ベルリン ハイデルベルク、pp.  13–29、doi :10.1007/3-540-07389-2_179、ISBN 978-3-540-07389-5
• ブリッジズ、ダグラス・S. (1994)、「抽象複雑性理論」、Computability、第146巻、ニューヨーク、ニューヨーク州：Springer New York、pp.  93– 115、doi :10.1007/978-1-4612-0863-1_7、ISBN 978-1-4612-6925-0