"NP-hard" Doesn't Mean That You Can't Solve It

(You can watch the video version of this post on YouTube.)

Now a lot of the time, the way that NP-hard problems get talked about is as if you can’t solve them. Well, probably not in worst-case polynomial time on a deterministic Turing machine - sure, but exponential time is not like .. forbidden, it’s just: a lot. Computers are pretty fast though and sometimes the instances that you want to solve aren’t that large anyway. Depending on both the problem and the methods, you can actually solve larger instances than you might expect. You can do Independent Set with hundreds of vertices no problem; under some circumstances you can do Knapsack with millions of items in less than a minute.

And then there are of course heuristics and approximation algorithms, which are also massively relevant in practice, but I’ll focus on colouring INSIDE the lines here: let’s actually “solve” the problem as stated.

First of all, there is a humongous difference between $n!$ and $2^n$. Brute forcing a permutation stops being fun after about 10 or 12, but $2^n$ time gets you up to about $n=30$ quite comfortably if the constant factors are low. Luckily a lot of the time you can actually use dynamic programming to get permutation problems down to $2^n$ time at a cost in space. Take a look at the Held-Karp algorithm for traveling salesman, for example.

Then there is “solver” software, especially for SAT and ILP - these are sophisticated pieces of software for satisfiability and integer linear programs. You may recognise that both of these problems are NP-hard themselves, but there is a lot of algorithmic and practical knowledge in these specific solvers - as well as years or even decades of software engineering and tuning. So it actually tends to work out quite well to reduce your problem TO satisfiability or to ILP. Some of these solvers are commercial, but they tend to have free academic licenses for students and staff. Just to throw some names out: Cplex, Gurobi and SCIP for linear programs, and minisat and Cadical for satisfiability - but especially for SAT there are many options with particular strengths. Be sure to shop around.

Next, there’s the concept of “moderately exponential”-time algorithms; that’s actually an entire field of study. NP-hardness does NOT mean that the only solution is brute force. For example, it’s fairly easy to do Independent Set in worst case about $1.7^n$ and that’s an exponential improvement over the trivial $2^n$. You can actually do much better still, but uh I’m sure we’ll talk about it some other time. My point here is that polynomial time algorithms aren’t the only place where you get to be smart and in some sense, it matters even more.

Finally for today, there’s the concept of “fixed-parameter tractability” - “FPT” - which is kind of a way to formalise that the number of vertices, or the input length or whatever, may not be what really matters. There’s an algorithm for deciding k-Vertex Cover, for example, with runtime $O(2^k \cdot n)$. For fixed k, that’s linear time on this NP-hard problem! Now of course $k$ could be linear in $n$ and then this is exponential - but it tells us something about what makes an instance hard, and it’s not necessarily the size of the graph. If you’re only going to get instances with low $k$, or if you only care about the result if $k$ is low, this is a really interesting framework - it’s a little bit more subtle than this, but you can look that up if you need to. Some more keywords here are “kernelisation” and uh “fine-grained complexity.”

Yeah, so: “NP-hard” does not mean that you can’t solve it.