圧縮定理のソースを表示

'''圧縮定理'''（あっしゅくていり、{{lang-en-short|compression theorem}}）は[[計算複雑性理論]]における[[計算可能関数]]の複雑性に関する重要な定理である。

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

==圧縮定理==
いま[[計算可能関数|部分計算可能関数]]の[[ナンバリング_(計算可能性理論)|アクセプタブル・ナンバリング]] <math>\varphi</math> と[[ブラムの公理|ブラム複雑性測度]] <math>\Phi</math> を所与とする。このとき上限 <math>f</math> のもとでの複雑性クラスは次のように定義される：
:<math>\mathrm{C}(f):= \{\varphi_i \in \mathbf{R}^{(1)} | (\forall^\infty x) \, \Phi_i (x) \leq f(x) \}.</math>

このとき[[計算可能関数|全域計算可能関数]]  <math>f</math> が存在して、任意の指標 <math>i</math> に対して次が成り立つ：
:<math>\mathrm{Dom}(\varphi_i) = \mathrm{Dom}(\varphi_{f(i)}),</math>
:<math>\mathrm{C}(\varphi_i) \subsetneq \mathrm{C}(\varphi_{f(i)}).</math>

==関連項目==
*[[ブラムの公理]]
*[[ブラムの加速定理]]
*[[マヌエル・ブラム]]

==参考文献==
*{{citation|title=Computation and Automata|volume=25|series=Encyclopedia of Mathematics and Its Applications|first=Arto|last=Salomaa|authorlink=Arto Salomaa|publisher=Cambridge University Press|year=1985|isbn=9780521302456|contribution=Theorem 6.9|pages=149–150|url=https://books.google.co.jp/books?id=IblDi626fBAC&pg=PA149&redir_esc=y&hl=ja}}.
*{{citation|title=Computational Complexity: A Quantitative Perspective|volume=196|series=North-Holland Mathematics Studies|first=Marius|last=Zimand|publisher=Elsevier|year=2004|isbn=9780444828415|contribution=Theorem 2.4.3 (Compression theorem)|page=42|url=https://books.google.co.jp/books?id=j-nhMYoZhgYC&pg=PA42&redir_esc=y&hl=ja}}.

{{デフォルトソート:あつしゆくていり}}
[[Category:計算複雑性理論]]
[[Category:数学基礎論の定理]]
[[Category:数学に関する記事]]