With care you can explain major ideas and results in computational complexity to the general public, like the P v NP problem, zero-knowledge proofs, the PCP theorem and Shor's factoring algorithms in a way that a curious non-scientist can find interesting. Quanta magazine keeps coming back to complexity. because we have a inherently interesting field.
So why am I having such a difficult time with the new Ryan Williams result, that time can be simulated in nearly quadratically less memory, or more precisely DTIME(\(t(n)\)) \(\subseteq\) DSPACE(\(\sqrt{t(n)\log t(n)}\)), based on the Cook-Mertz space-efficient tree evaluation algorithm.
Many results in complexity are quite specialized and technical but this shouldn't be one of them. Ryan's result involves a major new relationship between time and memory, the two most basic resource measures that goes back to the 1960s. Everybody understands time--waiting while their computer or phone is spinning. They know about memory, at least that you have to pay more for an iPhone with more of it. Yet still I'm challenged to explain this result.
Maybe because for historical reasons we use SPACE instead of MEMORY, or the pesky \(\log t(n)\) factor. Someone said they got lost in the logarithms. But we can talk about the gist of the result without mention space or logarithms.
It might be the \(t(n)\). We take for granted that we measure resources as a function of the problem size but outsiders could find it a challenging concept. For P v NP I just talk about efficient computation, here you can't avoid more specific running times.
Or maybe people don't think about time and memory. Most operations on a computer happen close to instantaneously. Nobody thinks about memory unless they run out of it.
Or because we don't have good real-world examples. When would you prefer a space \(\sqrt{t(n)}\) time \(2^\sqrt{t(n)}\) procedure to a space \(t(n)\) time \(t(n)\) algorithm?
AI is supposed to be good at this. OK, Claude take it away.
Ryan Williams' breakthrough paper shows that computers can solve complex problems using far less memory than previously thought possible. For 50 years, computer scientists believed that problems requiring a certain amount of time (t) needed at least t divided by a small factor of memory. Williams proved that these same problems can actually be solved using only about the square root of t memory. He achieved this by connecting these problems to the Tree Evaluation problem and leveraging a recent algorithm by Cook and Mertz. This result makes significant progress toward resolving the longstanding P versus PSPACE problem, suggesting that many algorithms could potentially run efficiently on devices with much less memory than we currently use.
Imagine a navigation app trying to find the optimal route through a complex city network. Before this discovery, engineers believed that calculating detailed routes required either substantial memory or accepting slower performance on memory-limited devices. Williams' theorem suggests these calculations could run using dramatically less memory—potentially reducing requirements from 100 MB to just 10 KB (roughly the square root). This breakthrough could enable sophisticated navigation features on devices with severe memory constraints, such as smart watches, older phones, or embedded car systems, allowing them to handle complex routing problems with multiple stops or constraints without performance degradation.
It's funny to see how the AI starts bullshitting in the second paragraph. And for those who don't understand the result, it might even be vaguely plausible.
ReplyDeleteI think Claude was trying to do what ordinary people want: give an example using specific numbers. It just failed miserably. Ordinary folks don't have a vivid intuitive sense of "memory that's the square root of time". They probably wonder: if you take the square root of ten seconds, how many megabytes is that? You can say that's not the right question, but then you have to tell them what is the right question.
ReplyDeleteTBH That second paragraph reminds me a lot of closing paragraphs in a lot of pop science journalism that usually exaggerates the importance of whatever result the article is about.
ReplyDeleteThe first paragraph is also bullshit! "computer scientists believed that problems requiring a certain amount of time (t) needed at least t divided by a small factor of memory": That is not true!
ReplyDeleteFor the difficulty of the result, I guess that one point is that the standard TIME(t) ⊂SPACE(t) is actually TIME(t) ⊂TIME-SPACE(t), while the new result does not preserve time. But maybe, an explanation can be tried that way: "An algorithm that uses time t uses a memory of size at most proportional to t. A question becomes: ok but if we simply try to replace our algorithm by an equivalent one that uses the smallest possible amount of memory, whatever time it takes, how small can this memory be? As far as we know, we are not able to rule out that an exponentially smaller memory could be sufficient (that is of size proportional to log t). But the only known result was much more modest: a memory of size t/log t is sufficient. Ryan's new result is that √(t log t) is sufficient: the previous result was almost t, the new is almost √t."
Here's my attempt.
ReplyDeleteThe theorem says that if an algorithm runs for t steps, then it can be simulated by another algorithm that uses roughly sqrt(t) bits of memory. This is surprising, because the original algorithm might use up to t bits of memory. The "catch" is that the new algorithm is very slow, i.e., it takes way more than t steps. Consequently, the theorem is not necessarily very useful for practical computing. Nevertheless, the theorem has a ton of scientific value, because it tells us something new and surprising about how time and memory constraints affect computation.
I had a similar problem trying to explain this to some family members. I started by trying to say that this result implies that all fast algorithms can be run using very little memory. But when I add the caveat that the low memory algorithm is so slow that no one would want to use it, they get confused again. Then I said it makes a little progress on a very fundamental problem that would have serious implications, even if this isn't enough progress to make most of those implications. That seemed to satisfy them, but a similar thing could be said about nearly every result in complexity theory.
ReplyDeleteGraphs are not usually as aesthetically pleasing as other graphics but in the form of a gif, they could be a nice addition to an article on complexity theory. Quanta Magazine has a YouTube video, 11 minutes and 12 seconds into which they zoom further and further out of a graph of f(n) = 2^n. https://youtu.be/pQsdygaYcE4?t=672
ReplyDeleteYou are challenged because practically it has no significant consequences and conceptually there is no reason why this might not be true.
ReplyDeleteThe importance of this result is just the fact that we have made some epsilon progress in an area that has been extremely hard to make any progress for decades.
Put differently, if you didn't know this is a progress in a very hard research area, would you be excited about this result?
ReplyDeleteI for one can say I definitely would not be.
It is blatantly obvious you can reuse space, reusing time is much harder. Until last month i had only heard of an upper limit time = e^space or something. Now someone found the lower limit near sqrt, I would have guessed much higher.
ReplyDelete