Catalytic computing

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (February 2025)

Catalytic computing is a technique in computer science, relevant to complexity theory, that uses full memory, as well as empty memory space, to perform computations.^[1][2] Full memory is memory that begins in an arbitrary state and must be returned to that state at the end of the computation, for example important data.^[2] It can sometimes be used to reduce the memory needs of certain algorithms, for example the tree evaluation problem.^[1] It was defined by Buhrman, Cleve, Koucký, Loff, and Speelman in 2014^[3] and was named after catalysts in chemistry, based on the metaphorically viewing the full memory as a "catalyst", a non-consumed factor critical for the computational "reaction" to succeed.^[1]

The complexity class CSPACE(s(n)) is the class of sets computable by catalytic Turing machines whose work tape is bounded by s(n) tape cells and whose auxiliary full memory space is bounded by ${\displaystyle 2^{s(n)}}$ tape cells.^[2] It has been shown that CSPACE(log(n)), or catalytic logspace, is contained within ZPP and, importantly, contains TC¹.^[2]