Reversible Space–Time Trade-offs

The pebble game handed us one specific bargain: halve recursively, and space T collapses to about \log_2 T pebbles while time swells to T^{1.585}. But 1.585 is not a law of nature — it is the price at one setting of a dial. Why cut each stretch into two pieces? Cut it into k, and a whole family of strategies appears, each trading a little more space for a smaller time exponent. Tuning that dial all the way gives the definitive theorem of the subject — Bennett's 1989 result that reversible simulation can come arbitrarily close to no time blow-up at all, at a space cost only logarithmically worse than the original machine's.

The k-ary pebbling behind the theorem

Generalise the halving strategy. Chop the T-step run into k big segments; chop each of those into k again, and so on for n levels, down to segments of some base length m (so T = m \cdot k^n). To pebble the end of a stretch at any level: sweep forward planting a checkpoint after each of its k sub-stretches, then sweep backwards un-planting the k-1 intermediate ones. That is k forward sub-simulations plus k-1 cleanup sub-simulations: 2k-1 sub-problems per level. Compounding over n levels:

\text{time} \;\approx\; m\,(2k-1)^n \;=\; T^{\log_k(2k-1)}, \qquad \text{exponent} \;=\; \frac{\log(2k-1)}{\log k} \;=\; 1 + \varepsilon_k .

For k=2 the exponent is \log_2 3 \approx 1.585 — our old halving bargain. For k=10 it is \log_{10} 19 \approx 1.28; for k=100, about 1.15. The exponent creeps down towards 1 as k grows. Meanwhile the board holds up to k pebbles per level across n \approx \log_k T levels — each pebble a full configuration of size S — for space of order k \, S \log_k T: still only logarithmically above S in T, but with a constant that swells with k. Push the dial and you get:

for every \varepsilon > 0: an irreversible computation of time T and space S can be simulated reversibly in time O(T^{1+\varepsilon}) and space O(S \log T);
the hidden constants depend on \varepsilon — a smaller \varepsilon means a larger branching factor k and fatter constants;
refinements (Levine–Sherman; analysed further by Li and Vitányi) sharpen the accounting to time \Theta\!\big(T^{1+\varepsilon}/S^{\varepsilon}\big) and show the space constant grows like \varepsilon\,2^{1/\varepsilon} — exponentially in 1/\varepsilon.

The dial, drawn

Here is the whole family at a glance: the time exponent 1+\varepsilon_k = \log(2k-1)/\log k against the branching factor k. It falls steeply at first — going from k=2 to k=4 already buys a lot — then flattens into a long, expensive crawl towards the dashed ideal of exponent 1, which the curve approaches but never reaches.

The two ends of the dial

It pays to keep the extremes in view — every strategy in this subject lives between these two:

Strategy	Time	Space
Full history (journal everything)	\approx 2T	O(T)
Halving, k=2	\approx T^{1.585}	O(S \log T)
Maximal recompute, large k	O(T^{1+\varepsilon})	O(S \log T), constant \sim \varepsilon 2^{1/\varepsilon}

A concrete feel for the middle row: take k=4 and n=3 levels, so T = 64 base segments. Each level multiplies the work by 2k-1 = 7, so the simulation performs 7^3 = 343 base-segment runs where the irreversible machine performed 64 — a factor of about 5.4, matching 64^{\,\log_4 7 - 1} = 64^{0.40}. The exponent is not an abstraction; it is compound interest on cleanup sweeps.

The theorem says "for every \varepsilon > 0", and it is tempting to wave at that and conclude "so effectively time O(T) and space O(S \log T) together." No. Each fixed \varepsilon is a different simulation with its own constants, and those constants explode as \varepsilon \to 0: driving the exponent down means a huge branching factor k \approx 2^{1/\varepsilon}, hence that many pebbles held per recursion level — the Levine–Sherman accounting puts the space constant at roughly \varepsilon\,2^{1/\varepsilon}, exponential in 1/\varepsilon. Setting \varepsilon = 0 exactly would need infinitely many pebbles per level. Whether some cleverer scheme could achieve time O(T) and space O(S) simultaneously is a real question — pebbling lower bounds say no strategy within this game can, and the wider question returns with a shock in the next lesson.

Where does the extra \log T factor actually live? Count what the simulator must hold at its busiest moment: one partially finished stretch at each of the n \approx \log_k T recursion levels — the outermost sweep is midway through its k checkpoints, one of those sub-stretches is midway through its own, and so on down. Each level pins O(k) checkpoints of size O(S), giving O(k\,S \log_k T) in total. The \log T is the depth of the recursion made physical — a stack of half-finished journals, one per level. This also explains the space-complexity connection required here: S multiplies everything, so machines with tiny workspace (the sublinear-space classes) are exactly the ones for which reversible simulation is cheapest.