圧縮定理

圧縮定理（あっしゅくていり、）は計算複雑性理論における計算可能関数の複雑性に関する重要な定理である。
この定理は計算可能な上限で抑えられる最大の複雑性クラス（それは全ての計算可能関数を含む）が存在しないことを述べる。
圧縮定理.
いま部分計算可能関数のアクセプタブル・ナンバリング formula_1 とブラム複雑性測度 formula_2 を所与とする。このとき上限 formula_3 のもとでの複雑性クラスは次のように定義される：
このとき全域計算可能関数 formula_3 が存在して、任意の指標 formula_6 に対して次が成り立つ：