flâneur

Why SAT Is Hard

matklad.github.io · 1,522 words · saved by 1 readers

An introductory post about complexity theory today! It is relatively well-known that there exist so-called NP-complete problems --- particularly hard problems, such that, if you solve one of them efficiently, you can solve all of them efficiently. I think I've learned relatively early that, e.g., SAT is such a hard problem. I've similarly learned a bunch of specific examples of equally hard problems, where solving one solves the other. However, why SAT is harder than any NP problem remained a mystery for a rather long time to me. It is a shame --- this fact is rather intuitive and easy to understand. This post is my attempt at an explanation. It assumes some familiarity with the space, but it's not going to be too technical or thorough.

An introductory post about complexity theory today! It is relatively well-known that there exist so-called NP-complete problems — particularly hard problems, such that, if you solve one of them efficiently, you can solve all of them efficiently. I think I’ve learned relatively early that, e.g., SAT is such a hard problem. I’ve similarly learned a bunch of specific examples of equally hard problems, where solving one solves the other. However, why SAT is harder than any NP problem remained a mystery for a rather long time to me. It is a shame — this fact is rather intuitive and easy to understa

related reading