圧縮定理

圧縮定理（あっしゅくていり、英: compression theorem）は計算複雑性理論における計算可能関数の複雑性に関する重要な定理である。

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

圧縮定理

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

$\mathrm {C} (f):=\{\varphi _{i}\in \mathbf {R} ^{(1)}|(\forall ^{\infty }x)\,\Phi _{i}(x)\leq f(x)\}.$

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

$\mathrm {Dom} (\varphi _{i})=\mathrm {Dom} (\varphi _{f(i)}),$

$\mathrm {C} (\varphi _{i})\subsetneq \mathrm {C} (\varphi _{f(i)}).$

関連項目

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

参考文献

• Salomaa, Arto (1985), “Theorem 6.9”, Computation and Automata, Encyclopedia of Mathematics and Its Applications, 25, Cambridge University Press, pp. 149–150, ISBN 9780521302456, https://books.google.co.jp/books?id=IblDi626fBAC&pg=PA149&redir_esc=y&hl=ja .
• Zimand, Marius (2004), “Theorem 2.4.3 (Compression theorem)”, Computational Complexity: A Quantitative Perspective, North-Holland Mathematics Studies, 196, Elsevier, p. 42, ISBN 9780444828415, https://books.google.co.jp/books?id=j-nhMYoZhgYC&pg=PA42&redir_esc=y&hl=ja .