Reversible Complexity Classes

Time to place reversibility on the master map of computer science — the zoo of complexity classes. We know reversible machines compute everything computable; the open ledger is the resource bill. The trade-off theorems suggested a gloomy folk rule: reversibility taxes you somewhere — pay in space (the history) or pay in time (the recomputation), but pay. This lesson delivers the two headline results, and the second is a genuine shock: for space, the tax turns out to be exactly zero.

Reversible classes, defined

The definitions are the obvious ones. \mathrm{RevTIME}(f) is the class of problems decided by a reversible Turing machine within O(f(n)) steps; \mathrm{RevSPACE}(f) the class decided by a reversible machine touching O(f(n)) tape cells. The interesting question is how these compare with their unrestricted cousins \mathrm{TIME}(f) and \mathrm{DSPACE}(f). One direction is free: every reversible machine is a machine, so \mathrm{RevTIME}(f) \subseteq \mathrm{TIME}(f) and \mathrm{RevSPACE}(f) \subseteq \mathrm{DSPACE}(f). All the drama is in the reverse inclusions.

For time, Bennett's trade-off already answers within a whisker: \mathrm{TIME}(T) \subseteq \mathrm{RevTIME}(T^{1+\varepsilon}) for every \varepsilon > 0. In particular the polynomial world is safe — a polynomial raised to the power 1+\varepsilon is still a polynomial, so reversible P equals P. Whether the slight blow-up can be removed entirely — is \mathrm{RevTIME}(T) = \mathrm{TIME}(T)? — is open, and the pebbling lower bounds make "no" the safe bet.

The shock: reversible space costs nothing

For space, the folk rule predicted a tax of at least a \log T factor — that is what every pebbling strategy pays. In 2000, Lange, McKenzie and Tapp proved the folk rule dead wrong:

\mathrm{RevSPACE}(S) = \mathrm{DSPACE}(S) for every space bound S(n) \geq \log n — reversibility costs no space at all;
the simulation reuses the very cells of the original machine: space O(S), no history, no checkpoints;
the price is paid entirely in time — the traversal can run for exponentially many steps in S;
combined with Bennett: reversibility is free in space (LMT), nearly free in time (Bennett), but no known simulation is free in both at once.

How can a simulation possibly avoid the history? By changing the game. A space-S machine has finitely many configurations — at most exponentially many in S. Its step map draws a configuration graph on them, and the run from the start configuration is a path through a component of that graph that funnels into the accepting configuration. The LMT machine never journals this path. Instead it treats the component as territory to be explored: the predecessor relation organises the configurations reachable backwards from the accept configuration into a spanning tree, and a walk that goes "first child, then next sibling, else back to the parent" — an Euler tour, the same trick that lets you trace a maze with your hand on one wall — visits the whole tree deterministically in both directions. Each traversal step is computable from the current configuration alone (simulate neighbours to find your place in the sibling order), so the walk needs no memory beyond the current configuration itself. And a walk that is deterministic forwards and backwards is precisely a reversible computation.

The picture

The figure shows a toy configuration tree rooted at the accepting configuration. First the forward step map, with its information-destroying funnels; then the Euler tour that replaces it — one thread winding around the whole tree, entering and leaving every configuration exactly once in each direction. The thread has in-degree one everywhere, which is reversibility incarnate — and it stores nothing, which is why the space bill is zero. The cost is stark in the picture too: the tour visits every edge twice, and the tree can hold exponentially many configurations, so the walk can take exponential time to find the start configuration and certify acceptance.

The scoreboard

Putting the module's results side by side — this is the state of the art, and the open wound, in three lines:

Resource	Result	Price
Time	\mathrm{TIME}(T) \subseteq \mathrm{RevTIME}(T^{1+\varepsilon}) (Bennett 1989)	space O(S\log T)
Space	\mathrm{RevSPACE}(S) = \mathrm{DSPACE}(S) (LMT 2000)	time possibly exponential
Both at once	open — believed impossible in general	pebbling lower bounds say no strategy of that kind can

Each headline theorem protects one resource by sacrificing the other. Whether some yet-unimagined simulation could preserve time and space simultaneously is the standing open problem of the field; within the pebble-game framework the answer is provably no, so a positive answer would need an idea as fresh as LMT's tour was.

It is dangerously easy to summarise this lesson as "Bennett handled time, LMT handled space — reversibility is essentially free." Look again at the price column. Bennett's near-perfect time comes bundled with a space blow-up to S \log T; LMT's perfect space comes bundled with potentially exponential time. They are two different simulations at opposite corners of the trade-off square, and you cannot run both at once on the same computation. The honest summary: each resource can be protected separately, and protecting both simultaneously is believed impossible. Classes built from a single resource bound (\mathrm{P}, \mathrm{PSPACE}) absorb reversibility without flinching; it is the simultaneous time–space behaviour where reversibility genuinely bites.

The Euler tour's reversibility is worth savouring, because no step of it is stored anywhere. Put your hand on one wall of a maze and walk without ever lifting it: at every junction, the rule "take the next passage clockwise from the one you came in by" determines your move — and, crucially, the rule read backwards ("take the next passage anticlockwise") is equally deterministic. The walk is a bijection on (configuration, direction-of-travel) pairs. That is the whole reversibility proof, in a maze. The LMT machine's genius is doing this on a tree it can never see whole: at each moment it re-derives its local position — who is my parent? am I my parent's last child? — by simulating single steps of the original machine, spending time lavishly to avoid writing down so much as one breadcrumb.