For Algorithms, a Little Memory Outweighs a Lot of Time

What’s more, this result — a statement about what you can compute given a certain amount of space — also implies a second result, about what you cannot compute in a certain amount of time. This second result isn’t surprising in itself: Researchers expected it to be true, but they had no idea how to prove it. Williams’ solution, based on his sweeping first result, feels almost cartoonishly excessive, akin to proving a suspected murderer guilty by establishing an ironclad alibi for everyone else on the planet. It could also offer a new way to attack one of the oldest open problems in computer science.

“It’s a pretty stunning result, and a massive advance,” said Paul Beame, a computer scientist at the University of Washington. “It’s a little bit less of a surprise that it’s Ryan doing this.”

Space to Roam

Williams, 46, has an open, expressive face and a hint of gray in his hair. His office, which looks out over the colorful spires of MIT’s Stata Center, is another illustration of the creative use of space. A pair of yoga mats have transformed a window ledge into a makeshift reading nook, and the desk is tucked into an oddly shaped corner, freeing up room for a couch facing a large whiteboard brimming with mathematical scribblings.

MIT is a long way from Williams’ childhood home in rural Alabama, where there was no shortage of space. He grew up on a 50-acre farm and first saw a computer at age 7, when his mother drove him across the county for a special academic enrichment class. He recalled being transfixed by a simple program for generating a digital fireworks display.

“It was taking a random color and sending it in a random direction from the middle of the monitor,” Williams said. “You couldn’t have predicted what picture you’re going to get.” The world of computers seemed a wild and wonderful playground, full of infinite possibilities. Young Williams was hooked.

“I was writing programs to myself, on paper, to be run on a future computer,” he said. “My parents didn’t really know what to do with me.”

As he grew older, Williams advanced from imaginary computers to real ones. For his last two years of high school, he transferred to the Alabama School of Math and Science, a prestigious public boarding school, where he first encountered the theoretical side of computer science.

“I realized that there was a wider world of things out there, and that there was a way to think mathematically about computers,” he said. “That’s what I wanted to do.”

Williams was especially drawn to a branch of theoretical computer science called computational complexity theory. It deals with the resources (such as time and space) that are needed to solve computational problems such as sorting lists or factoring numbers. Most problems can be solved by many different algorithms, each with its own demands on time and space. Complexity theorists sort problems into categories, called complexity classes, based on the resource demands of the best algorithms for solving them — that is, the algorithms that run fastest or use the least amount of space.

But how do you make the study of computational resources mathematically rigorous? You won’t get far if you try to analyze time and space by comparing minutes to megabytes. To make any progress, you need to start with the right definitions.

Getting Resourceful

Those definitions emerged from the work of Juris Hartmanis, a pioneering computer scientist who had experience making do with limited resources. He was born in 1928 into a prominent Latvian family, but his childhood was disrupted by the outbreak of World War II. Occupying Soviet forces arrested and executed his father, and after the war Hartmanis finished high school in a refugee camp. He went on to university, where he excelled even though he couldn’t afford textbooks.

“I compensated by taking very detailed notes in lectures,” he recalled in a 2009 interview. “There is a certain advantage to [having] to improvise and overcome difficulties.” Hartmanis immigrated to the United States in 1949, and worked a series of odd jobs — building agricultural machinery, manufacturing steel and even serving as a butler — while studying mathematics at the University of Kansas City. He went on to a spectacularly successful career in the young field of theoretical computer science.

In 1960, while working at the General Electric research laboratory in Schenectady, New York, Hartmanis met Richard Stearns, a graduate student doing a summer internship. In a pair of groundbreaking papers they established precise mathematical definitions for time and space. These definitions gave researchers the language they needed to compare the two resources and sort problems into complexity classes.

One of the most important classes goes by the humble name “P.” Roughly speaking, it encompasses all problems that can be solved in a reasonable amount of time. An analogous complexity class for space is dubbed “PSPACE.”

The relationship between these two classes is one of the central questions of complexity theory. Every problem in P is also in PSPACE, because fast algorithms just don’t have enough time to fill up much space in a computer’s memory. If the reverse statement were also true, the two classes would be equivalent: Space and time would have comparable computational power. But complexity theorists suspect that PSPACE is a much larger class, containing many problems that aren’t in P. In other words, they believe that space is a far more powerful computational resource than time. This belief stems from the fact that algorithms can use the same small chunk of memory over and over, while time isn’t as forgiving — once it passes, you can’t get it back.

“The intuition is just so simple,” Williams said. “You can reuse space, but you can’t reuse time.”

But intuition isn’t good enough for complexity theorists: They want rigorous proof. To prove that PSPACE is larger than P, researchers would have to show that for some problems in PSPACE, fast algorithms are categorically impossible. Where would they even start?

A Space Odyssey

As it happened, they started at Cornell University, where Hartmanis moved in 1965 to head the newly established computer science department. Under his leadership it quickly became a center of research in complexity theory, and in the early 1970s, a pair of researchers there, John Hopcroft and Wolfgang Paul, set out to establish a precise link between time and space.

Hopcroft and Paul knew that to resolve the P versus PSPACE problem, they’d have to prove that you can’t do certain computations in a limited amount of time. But it’s hard to prove a negative. Instead, they decided to flip the problem on its head and explore what you can do with limited space. They hoped to prove that algorithms given a certain space budget can solve all the same problems as algorithms with a slightly larger time budget. That would indicate that space is at least slightly more powerful than time — a small but necessary step toward showing that PSPACE is larger than P.

With that goal in mind, they turned to a method that complexity theorists call simulation, which involves transforming existing algorithms into new ones that solve the same problems, but with different amounts of space and time. To understand the basic idea, imagine you’re given a fast algorithm for alphabetizing your bookshelf, but it requires you to lay out your books in dozens of small piles. You might prefer an approach that takes up less space in your apartment, even if it takes longer. A simulation is a mathematical procedure you could use to get a more suitable algorithm: Feed it the original, and it’ll give you a new algorithm that saves space at the expense of time.

Algorithm designers have long studied these space-time trade-offs for specific tasks like sorting. But to establish a general relationship between time and space, Hopcroft and Paul needed something more comprehensive: a space-saving simulation procedure that works for every algorithm, no matter what problem it solves. They expected this generality to come at a cost. A universal simulation can’t exploit the details of any specific problem, so it probably won’t save as much space as a specialized simulation. But when Hopcroft and Paul started their work, there were no known universal methods for saving space at all. Even saving a small amount would be progress.

The breakthrough came in 1975, after Hopcroft and Paul teamed up with a young researcher named Leslie Valiant. The trio devised a universal simulation procedure that always saves a bit of space. No matter what algorithm you give it, you’ll get an equivalent one whose space budget is slightly smaller than the original algorithm’s time budget.

“Anything you can do in so much time, you can also do in slightly less space,” Valiant said. It was the first major step in the quest to connect space and time.

But then progress stalled, and complexity theorists began to suspect that they’d hit a fundamental barrier. The problem was precisely the universal character of Hopcroft, Paul and Valiant’s simulation. While many problems can be solved with much less space than time, some intuitively seemed like they’d need nearly as much space as time. If so, more space-efficient universal simulations would be impossible. Paul and two other researchers soon proved that they are indeed impossible, provided you make one seemingly obvious assumption: Different chunks of data can’t occupy the same space in memory at the same time.

“Everybody took it for granted that you cannot do better,” Wigderson said.

Paul’s result suggested that resolving the P versus PSPACE problem would require abandoning simulation altogether in favor of a different approach, but nobody had any good ideas. That was where the problem stood for 50 years — until Williams finally broke the logjam.

First, he had to get through college.

Complexity Classes

In 1996, the time came for Williams to apply to colleges. He knew that pursuing complexity theory would take him far from home, but his parents made it clear that the West Coast and Canada were out of the question. Among his remaining options, Cornell stood out to him for its prominent place in the history of his favorite discipline.

“This guy Hartmanis defined the time and space complexity classes,” he recalled thinking. “That was important for me.”

Williams was admitted to Cornell with generous financial aid and arrived in the fall of 1997, planning to do whatever it took to become a complexity theorist himself. His single-mindedness stuck out to his fellow students.

“He was just super-duper into complexity theory,” said Scott Aaronson, a computer scientist at the University of Texas, Austin, who overlapped with Williams at Cornell.

But by sophomore year, Williams was struggling to keep up in courses that emphasized mathematical rigor over intuition. After he got a middling grade in a class on the theory of computing, the teacher suggested he consider other careers. But Williams wouldn’t give up his dream. He doubled down and enrolled in a graduate theory course, hoping that a stellar grade in the harder class would look impressive on his grad school applications. The professor teaching that graduate course was Hartmanis, by then an elder statesman in the field.

Williams began attending Hartmanis’ office hours every week, where he was almost always the only student who showed up. His tenacity paid off: he earned an A in the course, and Hartmanis agreed to advise him on an independent research project the following semester. Their weekly meetings continued throughout Williams’ time in college. Hartmanis encouraged him to cultivate an individual approach to complexity research and gently steered him away from dead ends.

“I was deeply influenced by him then,” Williams said. “I guess I still am now.”

But despite earning a coveted graduate research fellowship from the National Science Foundation, Williams was rejected by every doctoral program he applied to. On hearing the news, Hartmanis phoned a colleague, then turned around and congratulated Williams on getting accepted into a yearlong master’s program at Cornell. A year later Williams again applied to various doctoral programs, and with that extra research experience under his belt, he found success.

Williams continued working in complexity theory in grad school and the years that followed. In 2010, four years after receiving his doctorate, he proved a milestone result — a small step, but the largest in decades, toward solving the most famous question in theoretical computer science, about the nature of hard problems. That result cemented Williams’ reputation, and he went on to write dozens of other papers on different topics in complexity theory.

P versus PSPACE wasn’t one of them. Williams had been fascinated by the problem since he first encountered it in college. He’d even supplemented his computer science curriculum with courses in logic and philosophy, seeking inspiration from other perspectives on time and space, to no avail.

“It’s always been in the back of my mind,” Williams said. “I just couldn’t think of anything interesting enough to say about it.”

Last year, he finally found the opportunity he’d been waiting for.

Squishy Pebbles

The story of Williams’ new result started with progress on a different question about memory in computation: What problems can be solved with extremely limited space? In 2010, the pioneering complexity theorist Stephen Cook and his collaborators invented a task, called the tree evaluation problem, that they proved would be impossible for any algorithm with a space budget below a specific threshold. But there was a loophole. The proof relied on the same commonsense assumption that Paul and his colleagues had made decades earlier: Algorithms can’t store new data in space that’s already full.

For over a decade, complexity theorists tried to close that loophole. Then, in 2023, Cook’s son James and a researcher named Ian Mertz blew it wide open, devising an algorithm that solved the tree evaluation problem using much less space than anyone thought possible. The elder Cook’s proof had assumed that bits of data were like pebbles that have to occupy separate places in an algorithm’s memory. But it turns out that’s not the only way to store data. “We can actually think about these pebbles as things that we can squish a little bit on top of each other,” Beame said.

Cook and Mertz’s algorithm roused the curiosity of many researchers, but it wasn’t clear that it had any applications beyond the tree evaluation problem. “Nobody saw how central it is to time versus space itself,” Wigderson said.

Ryan Williams was the exception. In spring 2024, a group of students gave a presentation about the Cook and Mertz paper as their final project in a class he was teaching. Their enthusiasm inspired him to take a closer look. As soon as he did, an idea jumped out at him. Cook and Mertz’s method, he realized, was really a general-purpose tool for reducing space usage. Why not use it to power a new universal simulation linking time and space — like the one designed by Hopcroft, Paul and Valiant, but better?

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.”

Phrased in qualitative terms, Williams’ second result may sound like the long-sought solution to the P versus PSPACE problem. The difference is a matter of scale. P and PSPACE are very broad complexity classes, while Williams’ results work at a finer level. He established a quantitative gap between the power of space and the power of time, and to prove that PSPACE is larger than P, researchers will have to make that gap much, much wider.

That’s a daunting challenge, akin to prying apart a sidewalk crack with a crowbar until it’s as wide as the Grand Canyon. But it might be possible to get there by using a modified version of Williams’ simulation procedure that repeats the key step many times, saving a bit of space each time. It’s like a way to repeatedly ratchet up the length of your crowbar — make it big enough, and you can pry open anything. That repeated improvement doesn’t work with the current version of the algorithm, but researchers don’t know whether that’s a fundamental limitation.

“It could be an ultimate bottleneck, or it could be a 50-year bottleneck,” Valiant said. “Or it could be something which maybe someone can solve next week.”

If the problem is solved next week, Williams will be kicking himself. Before he wrote the paper, he spent months trying and failing to extend his result. But even if such an extension is not possible, Williams is confident that more space exploration is bound to lead somewhere interesting — perhaps progress on an entirely different problem.

“I can never prove precisely the things that I want to prove,” he said. “But often, the thing I prove is way better than what I wanted.”

Editor’s note: Scott Aaronson is a member of Quanta Magazine’s advisory board.