Catalytic computing

Catalytic computing is a model of computation in which an algorithm is given access to a block of memory that is already full of arbitrary data, in addition to whatever small amount of genuinely empty working space it would normally have, on the condition that the full memory must be restored to its original contents by the time the computation finishes. The full memory acts like a chemical catalyst: it takes part in the computation and can be read from and written to along the way, but it emerges unchanged at the end, so it is never consumed by the process even though it participates fully in it. This turns out to let some algorithms solve problems, such as certain tree-evaluation tasks, using far less genuinely empty space than would otherwise be required. The model was formally defined in 2014 by Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff and Florian Speelman, and catalytic logspace has since been shown to sit inside the complexity class ZPP while containing TC1.