Everyone who’s been around for a while recognizes that computing has gotten more powerful. Problems that were once intractable now seem almost trivial. It’s not really surprising; it’s progress. It’s what we expect. But it does suggest the question: is the progress because of advancements in hardware or because of improved algorithms being brought to bear on the problems.
It turns out that some researchers have looked at the question scientifically and written up their results. Even better, Vivek Haldar discusses the paper in one of his “Read A Paper” videos. Johannes Fichte, Markus Hecher, and Stefan Szeider have a paper that Haldar discusses that studies the problem of SAT solvers. SAT solving is a notoriously hard NP-Complete problem but we’re now routinely solving problems that were impossible 20 years ago. Is that because the hardware is so much better or is it because the algorithms are so much improved?
To answer that question, the authors ran today’s algorithms on 20 year old hardware and algorithms from twenty years ago on today’s hardware. It’s a clever experiment. If you don’t already know the answer, take a second to guess what the answer is before you watch Haldar’s video or read the paper. If you need a hint, the answer is just what you’d expect it would be.