Catalytic Computing Taps the Full Power of a Full Hard Drive

In the late 2000s, McKenzie and the pioneering complexity theorist Stephen Cook devised a problem that seemed like a promising candidate. Called the tree evaluation problem, it involves repeatedly solving a simpler math problem that turns a pair of input numbers into a single output. Copies of this math problem are arranged in layers like the matches in a tournament bracket: The outputs of each layer become the inputs to the next layer until there’s just one output remaining. Different tree evaluation algorithms represent different strategies for calculating this final output from the initial inputs — they might perform the calculations in a different order, or record the results of intermediate steps in a different way.

Many algorithms can solve the tree evaluation problem quickly, putting it in the class P. But every such algorithm must devote some memory to the numbers it’s working with, while also storing numbers it’s already calculated for use in later steps. That’s why Cook and McKenzie suspected that the problem was impossible to solve using limited memory. They formalized this intuition in a 2010 paper co-authored with three other researchers, and proved that every ordinary algorithm for solving the tree evaluation problem required too much memory to qualify for membership in L.

But their work didn’t rule out the possibility of bizarre algorithms that could somehow use the same piece of memory for storage and calculations simultaneously — the computing equivalent of using a page filled with important notes as scratch paper. Cook and McKenzie thought such outlandish algorithms couldn’t exist, and they were confident enough to put money on it: Anyone who could prove them wrong would win a cool $100.

Catalytic Conversion

Michal Koucký, a complexity theorist at Charles University in Prague, learned about the tree evaluation result from Cook during a 2011 sabbatical in Toronto. He grew determined to finish what Cook and McKenzie had started, by proving that there’s no way to do additional computations using memory that’s saving data for later. Koucký’s quest would lead him on an unexpected detour to the discovery of catalytic computing. Nearly a decade later, that discovery would inspire two young researchers to return to tree evaluation and settle Cook and McKenzie’s bet once and for all.

But back to the story of catalytic computing. It all started when Koucký visited colleagues in Amsterdam and posed the question that had been preoccupying him in simpler terms: What can you do with memory that’s already full?

“Nothing” was the obvious answer. “I thought, ‘OK, this is of course very useless, and we’re going to prove it,’” said Harry Buhrman, the leader of the Amsterdam group. “And then we couldn’t prove it.”

The breakthrough came months later, when Buhrman was visiting his frequent collaborator Richard Cleve at the University of Waterloo. They decided to focus on an extreme scenario, one where the full memory is very large. If a computer with little free memory can access this massive full memory, would that enable it to solve problems that would be impossible with the free memory alone? It’s like the “hard drive full of family photos” question, but with a hard drive the size of a data center.

If that extra data is untouchable — you can’t interact with it at all — then it definitely doesn’t help. But what if you’re allowed to tweak some of the bits encoding this data, as long as you promise to reset them when you’re done? You can’t simply keep a record of your changes, since that would take up even more space, so instead you’ll have to ensure that your changes are easily reversible. What’s more, you don’t get to choose the content of the extra data, so whatever you do must work for any possible initial configuration of bits.

Those are pretty stringent constraints, so it wasn’t obvious that the extra memory could ever prove useful. But to their surprise, Buhrman and Cleve showed that, if you tweak bits in just the right way, you really can get extra computational oomph out of a full memory.

“That was a shocker for everyone,” said Loff, who was a graduate student in Buhrman’s group at the time, working on the memory question with his fellow student Florian Speelman. The team soon extended the result to an even larger class of problems, and published their combined results in 2014.

They named the new framework catalytic computing, borrowing a term from chemistry. “Without the catalyst, the reaction would not have proceeded,” said Raghunath Tewari, a complexity theorist at the Indian Institute of Technology, Kanpur. “But the catalyst itself remains unchanged.”

Not Far From the Tree

A small band of researchers continued to develop catalytic computing further, but no one even tried to apply it to the tree evaluation problem that had initially inspired Koucký’s quest. For that problem, the remaining open question was whether a small amount of memory could be used for storage and computation simultaneously. But the techniques of catalytic computing relied on the extra, full memory being very large. Shrink that memory, and the techniques no longer work.

Still, one young researcher couldn’t help wondering whether there was a way to adapt those techniques to reuse memory in a tree evaluation algorithm. His name was James Cook, and for him the tree evaluation problem was personal: Stephen Cook, the legendary complexity theorist who invented it, is his father. James had even worked on it in graduate school, though he mostly focused on completely unrelated subjects. By the time he encountered the original catalytic computing paper in 2014, James was about to graduate and leave academia for software engineering. But even as he settled into his new job, he kept thinking about catalytic computing.

“I had to understand it and see what could be done,” he said.

For years, James Cook tinkered with a catalytic approach to the tree evaluation problem in his spare time. He gave a talk about his progress at a 2019 symposium in honor of his father’s groundbreaking work in complexity theory. After the talk, he was approached by a graduate student named Ian Mertz, who’d fallen in love with catalytic computing five years earlier after learning about it as an impressionable young undergrad.

“It was like a baby bird imprinting scenario,” Mertz said.

Cook and Mertz joined forces, and their efforts soon paid off. In 2020, they devised an algorithm that solved the tree evaluation problem with less memory than a necessary minimum conjectured by the elder Cook and McKenzie — though it was just barely below that threshold. Still, that was enough to collect on the $100 bet; conveniently for the Cooks, half of it stayed in the family.

But there was still work to do. Researchers had started studying tree evaluation because it seemed as if it might finally provide an example of a problem in P that’s not in L — in other words, a relatively easy problem that can’t be solved using very little memory. Cook and Mertz’s new method used less memory than any other tree evaluation algorithm, but it still used significantly more than any algorithm for a problem in L. Tree evaluation was down, but not out.

In 2023, Cook and Mertz came out with an improved algorithm that used much less memory — barely more than the maximum allowed for problems in L. Many researchers now suspect that tree evaluation is in L after all, and that a proof is only a matter of time. Complexity theorists may need a different approach to the P versus L problem.

Meanwhile, Cook and Mertz’s results have galvanized interest in catalytic computing, with new works exploring connections to randomness and the effects of allowing a few mistakes in resetting the full memory to its original state.

“We’ve not finished exploring what we can do with these new techniques,” McKenzie said. “We can expect even more surprises.”