圧縮定理

圧縮定理（あっしゅくていり、テンプレート:Lang-en-short）は計算複雑性理論における計算可能関数の複雑性に関する重要な定理である。

この定理は計算可能な上限で抑えられる最大の複雑性クラス（それは全ての計算可能関数を含む）が存在しないことを述べる。

圧縮定理

いま部分計算可能関数のアクセプタブル・ナンバリング $\phi$ とブラム複雑性測度 $\mathrm{\Phi }$ を所与とする。このとき上限 $f$ のもとでの複雑性クラスは次のように定義される：

$\mathrm{C}(f):=\{{\phi }_i\in {𝐑}^{(1)}|({\mathrm{\forall }}^{\mathrm{\infty }}x){\mathrm{\Phi }}_i(x)\le f(x)\}.$

このとき全域計算可能関数 $f$ が存在して、任意の指標 $i$ に対して次が成り立つ：

$\mathrm{D}\mathrm{o}\mathrm{m}({\phi }_i)=\mathrm{D}\mathrm{o}\mathrm{m}({\phi }_{f(i)}),$

$\mathrm{C}({\phi }_i)⊊\mathrm{C}({\phi }_{f(i)}).$

関連項目

• ブラムの公理
• ブラムの加速定理
• マヌエル・ブラム

参考文献

• テンプレート:Citation.
• テンプレート:Citation.