拉宾压缩定理

对于任何可构造函数 ，存在一个函数 ，使得对于所有函数 ，以下两个陈述是等价的：

1. 存在一个算法 ，使得对于所有输入 ， 在体积 内计算 。

2. 是可构造的，且 。

这里，体积 是所有步骤中活动边的总数，这是在特定输入上运行特定图灵机所需的状态更改次数。