圧縮定理

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

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

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

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

${\displaystyle \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 .