Space Saver

A new proof dramatically compresses the memory needed for computation

- Max Springer

ONCE UPON A TIME computers filled entire rooms, reading numbers from spinning tapes and churning them through wires to do chains of basic arithmetic. Today they slip into our pockets, performing in a tiny fraction of a second what used to take hours. But after decades of shrinking chips to pack as much computation as possible onto a machine, theorists are flipping the question: How little space is enough to get the job done?

This inquiry lies at the heart of computational complexity, a measure of the limits of what problems can be solved and at what cost in time and space. For nearly 50 years theorists could prove only that if solving a problem takes t steps, it should be possible using roughly t bits of memory—the 0s and 1s that a machine uses to record information. (Technically, that equation also incorporates log(t), but for the numbers involved this has little effect.)