Catalytic computing
Technique
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. 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. It can sometimes be used to reduce the memory needs of certain algorithms, for example the tree evaluation problem. It was defined by Buhrman, Cleve, Koucký, Loff, and Speelman in 2014 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.
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
2
s
(
n
)
{\displaystyle 2^{s(n)}}
tape cells. It has been shown that CSPACE(log(n)), or catalytic logspace, is contained within ZPP and, importantly, contains TC1.
Results
In 2020 J. Cook and Mertz used catalytic computing to prove to attack the tree evaluation problem (TreeEval), a type of pebble game introduced by Cook, McKenzie, Wehr, Braverman and Santhanam as an example where any algorithm for solving the problem would require too much memory to belong in the L complexity class, proving that in fact the conjectured minimum can be lowered and in 2023 they lowered the bound even further to space
O
(
log
n
log
log
n
)
{\displaystyle O(\log n\log \log n)}
, almost ruling out the problem as an approach to the question of whether L=P.
In 2025, Williams showed that the work of J. Cook and Mertz could be used to prove that every deterministic multitape Turing machine of time complexity
t
{\displaystyle t}
can be simulated in space
O
(
t
log
t
)
{\displaystyle O({\sqrt {t\log t}})}
improving the previous bound of
O
(
t
/
log
t
)
{\displaystyle O(t/\log t)}
by Hopcroft, Paul, and Valiant and strengthening the case in the negative for the question of whether PSPACE=P.
A related phenomenon to catalytic computing occurs in the study of space-efficient data structures. There exists pairs of data structure problems
A
{\displaystyle A}
and
B
{\displaystyle B}
such that any solution to
A
{\displaystyle A}
with
o
(
n
)
{\displaystyle o(n)}
-bit redundancy must incur super-constant-time queries, but such that a data structure which solves
A
{\displaystyle A}
and
B
{\displaystyle B}
with shared memory can support a total space redundancy of
o
(
n
)
{\displaystyle o(n)}
bits while offering constant-time queries for both problems
A
{\displaystyle A}
and
B
{\displaystyle B}
.
“Catalytic computing” enters the record as technique. Crown Archives preserves that source wording while asking what Catalytic, computing and Technique can confirm, complicate or overturn.
Why this record matters
“Catalytic computing” is worth following because a concise public description often conceals a longer documentary argument. Here, Catalytic, computing and Technique provides the most credible route into that argument.
Named sources, stable identifiers and responsible institutions provide the strongest route from overview to verifiable evidence. The source revision retrieved here is dated Jul 19, 2026. The linked authority identifier is Q133235650. None of the 0 selected statements returned an explicit reference. The first chronological checks are 2014, 2020, 2023 and 2025.
The absence of detail may reflect summary conventions rather than a lack of surviving documentation. The lead is largely declarative, so disagreement and counter-evidence require a deliberate search beyond the opening account. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.
How to read it
Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.
- Subject orientation
- Search vocabulary
- Locating named sources
The closest primary source, responsible institution and strongest cited specialist reference.
Three-step research path
- Establish the record: confirm the title “Catalytic computing”, its source revision and the description used here.
- Expand the search: follow Catalytic computing primary sources, Catalytic computing archive and Catalytic research across catalogues and specialist indexes.
- Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.
Questions for further research
- Which source most directly establishes the central claim about “Catalytic computing”?
- What terminology or title could unlock a more precise catalogue search?
- Which institution is responsible for the underlying evidence?
Search terms from this dossier
This entry incorporates text from “Catalytic computing” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.