Everyone who\u2019s been around for a while recognizes that computing has gotten more powerful. Problems that were once intractable now seem almost trivial. It\u2019s not really surprising; it\u2019s progress. It\u2019s 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.<\/p>\n
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 \u201cRead A Paper\u201d videos. Johannes Fichte, Markus Hecher, and Stefan Szeider have a paper<\/a> that Haldar discusses<\/a> that studies the problem of SAT solvers. SAT solving is a notoriously hard NP-Complete problem but we\u2019re 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?<\/p>\n To answer that question, the authors ran today\u2019s algorithms on 20 year old hardware and algorithms from twenty years ago on today\u2019s hardware. It\u2019s a clever experiment. If you don\u2019t already know the answer, take a second to guess what the answer is before you watch Haldar\u2019s video or read the paper. If you need a hint, the answer is just what you\u2019d expect it would be.<\/p>\n","protected":false},"excerpt":{"rendered":" Everyone who\u2019s been around for a while recognizes that computing has gotten more powerful. Problems that were once intractable now seem almost trivial. It\u2019s not really surprising; it\u2019s progress. It\u2019s what we expect. But it does suggest the question: is … Continue reading