拉賓壓縮定理

對於任何可建構函式 ，存在一個函式 ，使得對於所有函式 ，以下兩個陳述是等價的：

1. 存在一個演算法 ，使得對於所有輸入 ， 在體積 內計算 。

2. 是可構造的，且 。

這裡，體積 是所有步驟中活動邊的總數，這是在特定輸入上執行特定圖靈機所需的狀態更改次數。