How do time and space relate to computation? We have a new answer
Xuanyu Han/Getty Images
An astonishing discovery about the relationship between the amount of memory a computation requires and how long it takes has wowed computer scientists – although it isn’t clear if there are any practical applications.
“It kind of shakes my world view,” says Ryan Williams at the Massachusetts Institute of Technology, who made the discovery. “I’m still just shocked that it even exists.”
Time and memory space are the two main constraints on what we…
