This classic result is a way to convert any algorithm with time budget into a new algorithm with a smaller spatial budget. Williams saw that simulations based on quasi-cobbles would make the new algorithm much smaller in space usage, which is roughly the same as the square root of the original algorithm’s time budget. The new space efficiency algorithm will also be much slower, so simulations are unlikely to have practical applications. But from a theoretical perspective, this is nothing more than revolutionary.
For 50 years, researchers have believed that it is impossible to improve universal simulations of Hoproft, Paul and Valiant. Williams’ idea – if it works, not only will it beat their record – it will remove it.
“I thought about it, and I was like, ‘Well, that’s impossible to be true at all.’ He put it aside until July that day, when he tried to find the flaw in the argument and failed. After he realized there was no flaw, he spent months writing and rewriting the evidence to make it as clear as possible.
At the end of February, Williams finally put the finished paper online. Cook was as surprised as Mertz as everyone else. “I have to do anything else and then do anything else,” Merz said.
Valiant previewed Williams’ decades of results during get off work in the morning. He has been at Harvard for years, right on his way to Williams’s MIT office. They met before, but they didn’t know they lived in the same neighborhood until a day of snow in February, and they ran into each other on the bus a few weeks before the results were revealed. Williams described his evidence to amazing heroism and promised to send it along his paper.
“I was impressed,” Valiant said. “If you get the best math results in 50 years, you have to do the right thing.”
Pspace: The Last Boundary
Through his new simulation, Williams demonstrates that the computing power of space is a positive result: using algorithms with relatively less space can solve all problems that require more time. He then uses only a few lines of math, flips it out, and proves that the calculation power of time is a negative result: unless you use more time than space, at least some problems cannot be solved. Second, the narrow results are consistent with the researchers’ expectations. The weird part is how Williams gets there, first demonstrating the results that apply to all algorithms, no matter what problem they solve.
“I still have a hard time believing it,” Williams said. “It seems too good to achieve.”
Williams used Cook and Mertz’s technology to build a stronger connection between space and time, the first progress on the issue in 50 years.Photo: Katherine Taylor’s Quanta Magazine
Williams’ second result sounds like a long-term solution to the PSPACE problem. The difference lies in the scale. P and Pspace are very extensive complexity courses, while Williams’ results work on a more granular level. He established a quantitative gap between space and time forces and proved that Pspace is greater than P, which researchers will have to make larger, larger.
It was a tough challenge, similar to prying a crack in the sidewalk with a crowbar until it was as wide as the Grand Canyon. However, a modified version of Williams’ simulation process can be used, which repeats the key several times, saving some space each time. It’s like a way to repeatedly increase the length of the crowbar – making it big enough that you can pry anything open. Repeated improvements with the current version of the algorithm do not work, but the researchers don’t know if this is a basic limitation.
“It could be the ultimate bottleneck, or it could be a 50-year bottleneck,” Valiant said. “Or it could be something someone can fix next week.”
Williams will kick himself if the issue is resolved next week. Before he wrote his paper, he spent several months trying to expand the results. But even if such an expansion is impossible, Williams is confident that more space exploration will surely lead to some interesting place–may progress on a completely different issue.
“I can never prove what I want to prove,” he said. “But usually, what I prove is better than I want.”
Editor’s Note: Scott Aaronson is a member of the Quanta Magazine Advisory Board.
ability Reprinted under license by Quanta Magazine, an editorial independent publication of the Simons Foundation, whose mission is to enhance understanding of science through research developments and trends covering mathematics as well as physics and life sciences.
