Catalytic computing¶
A space-bounded computing model that temporarily uses memory with arbitrary initial contents while guaranteeing its exact restoration at the end.
Core Idea¶
Catalytic computing asks whether a machine can solve a problem with little clean work space while temporarily using a larger memory that already holds arbitrary data. The machine may read and modify that full memory, but it must return every auxiliary cell to its exact initial value for every possible initial configuration. A computed answer must survive the restoration. The arbitrary starting data and exact return distinguish the model from an extra blank work tape.[^ref-eaebd4ea1095]
The original catalytic-space work showed that logspace-uniform \(TC^1\) circuit evaluation can use logarithmic clean space and polynomial catalytic space. It did not prove that catalytic logspace is strictly stronger than ordinary logspace. Later directed-reachability algorithms show the contract in a different setting; a randomized answer may have one-sided error even though every run restores the auxiliary tape.[ref-eaebd4ea1095][ref-36896ff774c1]
Scope of Application¶
The named model belongs to theoretical computer science, particularly space complexity. A formal claim must specify the input problem and output, the amount of clean workspace, the size and arbitrary initial state of the auxiliary store, and why the store is exactly restored at termination. Merely sharing RAM or erasing some temporary changes is insufficient. Some variants add conditions such as fast access to original cells during the run; that local revertibility is stronger than ordinary final restoration.[ref-eaebd4ea1095][ref-36896ff774c1]
Clarity¶
Three tests keep the idea precise. First, the borrowed tape starts with any data, not guaranteed zeros. Second, only the designated clean tape supplies known free workspace under its stated bound. Third, after output, the entire borrowed tape must equal its own starting string. A correct answer with one changed cell fails the catalytic contract; an exactly restored randomized run may still give an erroneous answer within its stated error probability.[ref-eaebd4ea1095][ref-36896ff774c1]
Stepwise reversible operations can help implement restoration, but they do not define catalytic computing. The model requires a final-state invariant. Nor is the complexity class \(CSPACE(s)\) identical to a single catalytic machine: it groups problems solvable under specified resource bounds.[^ref-eaebd4ea1095]
Manages Complexity¶
The model condenses a proof into an explicit resource-and-restoration checklist while leaving the actual undo mechanism to the algorithm. The threshold-circuit construction uses transparent algebraic operations; a graph construction uses forward and reverse edge pushes, and its locally revertible randomized version also reverses random shifts on successful and aborted branches. Those are different ways to satisfy the same arbitrary-starting-memory obligation.[ref-eaebd4ea1095][ref-36896ff774c1]
Abstract Reasoning¶
To evaluate a proposed algorithm, begin with an arbitrary auxiliary string \(\tau\). Trace the temporary updates, the extraction of the answer, and every undo step. The proof must show that the final auxiliary string is \(\tau\) for every allowed starting string; with randomness, check every coin sequence separately from the chance of a correct answer. A proof that works only when the tape starts blank does not establish catalysis.[ref-eaebd4ea1095][ref-36896ff774c1]
Knowledge Transfer¶
The proof discipline can transfer from circuit evaluation to graph problems: arbitrary occupied memory can sometimes be used by extracting a result from reversible differences and then undoing the disturbance. The exact update operations, space costs, and output guarantees do not transfer automatically. Outside formal computation, borrowing and returning a resource is an analogy unless the clean-space and exact-restoration conditions are independently established.[ref-eaebd4ea1095][ref-36896ff774c1]
Example¶
In Buhrman and colleagues' uniform \(TC^1\) simulation, the target is circuit evaluation, the clean tape is logarithmic, the larger auxiliary tape begins arbitrarily, the program uses occupied registers temporarily, and the construction returns them to their initial state. In Cook and Pyne's directed-reachability work, graph-layer registers play the auxiliary role; forward pushes and random shifts are undone. The latter theorem allows one-sided answer error while still requiring restoration on every random branch.[ref-eaebd4ea1095][ref-36896ff774c1]
Relationships to Other Abstractions¶
Current abstraction Catalytic computing Domain-specific
Parents (1) — more general patterns this builds on
-
Catalytic computing is a kind of Abstract Machine Domain-specific
Catalytic computing is an abstract machine model specialized by bounded clean space, arbitrary-initial auxiliary memory and exact restoration.
Hierarchy paths (2) — routes to 2 parentless roots
- Catalytic computing → Abstract Machine → Formal System → Formalization → Representation → Abstraction
- Catalytic computing → Abstract Machine → Formal System → Formalization → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Catalytic computing sits in a sparse region of the domain-specific corpus (97th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Cell-Probe Model — 0.79
- EXPSPACE — 0.77
- Memory Management — 0.76
- Halting Problem — 0.76
- ESPACE — 0.75
Computed from structural-signature embeddings · 2026-10-17
Not to Be Confused With¶
An ordinary large blank work tape lacks arbitrary starting contents. Reversible computing constrains step behavior, whereas catalytic computing constrains the final auxiliary state.[^ref-eaebd4ea1095] Local revertibility additionally requires quick access to original borrowed cells mid-run.[^ref-36896ff774c1] Cook and Mertz's tree-evaluation branching-program results use catalytic ideas outside the catalytic-space setting and are not a second full formal-model instance on the sources inspected.[^ref-8d7475e74103]
The live Abstract Machine is the approved strict parent because catalytic computing is a specialized machine model with an additional two-memory restoration contract. The live Turing Machine's one-tape identity is not established across every catalytic instance, so no second edge is asserted.
References¶
[^ref-eaebd4ea1095]: Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman, “Computing with a Full Memory: Catalytic Space,” Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pp. 857–866. https://doi.org/10.1145/2591796.2591874 Full original author-hosted manuscript inspected at https://iuuk.mff.cuni.cz/~koucky/papers/catalytic.pdf ; definition in Abstract and Introduction, and the uniform \(TC^1\) containment in §4.1, Theorem 17. The source does not prove strict separation from ordinary logspace. [^ref-36896ff774c1]: James Cook and Edward Pyne, “Efficient Catalytic Graph Algorithms,” Leibniz International Proceedings in Informatics, ITCS 2026, article 43. https://doi.org/10.4230/LIPIcs.ITCS.2026.43 Full original publisher HTML inspected at https://drops.dagstuhl.de/storage/00lipics/lipics-vol362-itcs2026/html/LIPIcs.ITCS.2026.43/LIPIcs.ITCS.2026.43.html ; §1.1–1.4 and §3, especially Theorem 5, Theorem 13, Claim 14, and the Theorem 5 proof. Theorem 2 has smaller catalytic-space use without the same local-revertibility claim; Theorem 18 is a separate reduced-register branch. [^ref-8d7475e74103]: James Cook and Ian Mertz, “Catalytic Approaches to the Tree Evaluation Problem,” Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), 10 pages. https://doi.org/10.1145/3357713.3384316 Full original author-hosted paper inspected at https://iuuk.mff.cuni.cz/~iwmertz/papers/cm20.catalytic_approaches_to_the_tree_evaluation_problem.pdf ; Abstract and §§1.3–1.4 explicitly distinguish these branching-program results from the catalytic-space setting.