Plurrrr

A common assumption I see on the ‘net is that NP-complete problems are impossible to solve. I recently read that dependency management in Python is hard because package resolution is NP-complete. This is true in principle, but the reality is more complicated. When we say “NP-complete is hard” we’re talking about worst-case complexity, and the average-case complexity is often much more tractable. Many industry problems are “well-behaved” and modern SAT solvers can solve them quickly.

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.

Most command line programs that offer line editing – like bash, Python, GDB, psql, sqlite and more – do so using GNU readline. Readline's a powerful library that grants history, completion, movement and editing to programs that use it — and a stable and consistent set of keyboard shortcuts.

Shame, then, that even serious command line hackers never bother learning about its capabilities, as they can supercharge your command line productivity.