The researchers Buhrman and Cleve discovered that, despite initial doubts, tweaking bits in a certain way could harness additional computational power from a full memory. This surprising development was described as a “shocker” by Loff, a former graduate student in Buhrman’s group, who was involved in this research with fellow student Florian Speelman. Their findings were later extended to a broader range of problems, and they published their combined results in 2014.
They introduced a new framework called catalytic computing, drawing a parallel to chemistry, where a catalyst enables a reaction without undergoing any change itself. Complexity theorist Raghunath Tewari from the Indian Institute of Technology, Kanpur, compared this to the role of a catalyst in a chemical process.
While catalytic computing continued being developed by a small group of scientists, it wasn’t applied to the tree evaluation problem, which had been a significant concern for Koucký. The pivotal question remained whether a minimal amount of memory could be used for both storage and computation. Catalytic computing techniques required substantial additional memory, rendering them ineffective when memory was reduced.
A young researcher named James Cook, who had a personal connection to the tree evaluation problem through his father, Stephen Cook, a renowned complexity theorist, pondered if catalytic computing could somehow address the issue. James Cook, then making a transition to software engineering, continued exploring catalytic computing outside his professional obligations. He shared his progress at a 2019 symposium honoring his father’s work in complexity theory, where Ian Mertz, a graduate student, expressed keen interest in catalytic computing.
Cook and Mertz collaborated, and in 2020, they developed an algorithm capable of solving the tree evaluation problem with less memory than anticipated by Stephen Cook and McKenzie—though the reduction was slight. Nonetheless, this breakthrough allowed them to win a $100 bet, with part of the winnings remaining within the Cook family.
Despite their successful algorithm, the tree evaluation problem had attracted attention because it seemed to represent a problem in P that wasn’t in L (solvable easily but not with minimal memory). Although Cook and Mertz’s solution used less memory than any other existing algorithm for tree evaluation, it still required more memory than algorithms for problems classified as L. The final challenge persisted.
In 2023, Cook and Mertz released an improved algorithm using significantly less memory, nearing the limit allowed for problems in L. This led many researchers to suspect that tree evaluation might indeed belong to the class L, with a proof a likely future development. This will necessitate alternative approaches to the P versus L conundrum among complexity theorists.
Cook and Mertz’s advancement spurred renewed interest in catalytic computing, leading to further studies exploring its connections to randomness and the effects of permitting certain errors when resetting the full memory to its original state. McKenzie remarked on the unresolved potential of these new techniques, indicating that more breakthroughs could be on the horizon.
