That classic result was a way to transform any algorithm with a given time budget into a new algorithm with a slightly smaller space budget. Williams saw that a simulation based on squishy pebbles would make the new algorithm’s space usage much smaller—roughly equal to the square root of the original algorithm’s time budget. That new space-efficient algorithm would also be much slower, so the simulation was not likely to have practical applications. But from a theoretical point of view, it was nothing short of revolutionary.
For 50 years, researchers had assumed it was impossible to improve Hopcroft, Paul and Valiant’s universal simulation. Williams’ idea—if it worked—wouldn’t just beat their record—it would demolish it.
“I thought about it, and I was like, ‘Well, that just simply can’t be true,’” Williams said. He set it aside and didn’t come back to it until that fateful day in July, when he tried to find the flaw in the argument and failed. After he realized that there was no flaw, he spent months writing and rewriting the proof to make it as clear as possible.
At the end of February, Williams finally put the finished paper online. Cook and Mertz were as surprised as everyone else. “I had to go take a long walk before doing anything else,” Mertz said.
Valiant got a sneak preview of Williams’ improvement on his decades-old result during his morning commute. For years, he’s taught at Harvard University, just down the road from Williams’ office at MIT. They’d met before, but they didn’t know they lived in the same neighborhood until they bumped into each other on the bus on a snowy February day, a few weeks before the result was public. Williams described his proof to the startled Valiant and promised to send along his paper.
“I was very, very impressed,” Valiant said. “If you get any mathematical result which is the best thing in 50 years, you must be doing something right.”
PSPACE: The Final Frontier
With his new simulation, Williams had proved a positive result about the computational power of space: Algorithms that use relatively little space can solve all problems that require a somewhat larger amount of time. Then, using just a few lines of math, he flipped that around and proved a negative result about the computational power of time: At least a few problems can’t be solved unless you use more time than space. That second, narrower result is in line with what researchers expected. The weird part is how Williams got there, by first proving a result that applies to all algorithms, no matter what problems they solve.
“I still have a hard time believing it,” Williams said. “It just seems too good to be true.”
Williams used Cook and Mertz’s technique to establish a stronger link between space and time—the first progress on that problem in 50 years. Photograph: Katherine Taylor for Quanta Magazine
... continue reading