圧縮定理

計算複雑性理論において、圧縮定理は計算可能関数の計算複雑性に関する重要な定理です。

定理は、計算可能な境界を持ち、すべての計算可能な関数を含む 最大の複雑性クラスは存在しないことを述べています。

圧縮定理

計算可能関数のゲーデル数と ブルーム複雑度尺度が与えられ、境界関数の複雑度クラスは次のように定義される。 ${\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)、「定理6.9」、計算とオートマトン、数学とその応用百科事典、第25巻、ケンブリッジ大学出版局、pp.  149– 150、ISBN 9780521302456。
• ジマンド、マリウス（2004）「定理2.4.3（圧縮定理）」、計算複雑性：定量的観点、ノースホランド数学研究、第196巻、エルゼビア、p.42、ISBN 9780444828415。