Strong and Weak NP-Hardness

In a previous post I talk about how NP-hardness doesn’t necessarily mean you can’t solve a problem. There are degrees to which this is true or not in practice, but there is also a distinction we can make at the level of complexity theory.

Consider the KNAPSACK problem with $n$ items and maximum weight $W$. There is a famous dynamic program for this with runtime order of $n\cdot W$. That looks polynomial, isn’t Knapsack NP-hard? Well, yeah, because $n\cdot W$ is not polynomial. I mean, it’s polynomial in $n$ and $W$, but not in the size of the input: as we discussed in another previous post, the size of $W$ is only $\log(W)$.

So in fact KNAPSACK can be NP-hard in spite of this DP, because we can write really large numbers with only a few symbols and then the DP is not efficient. But the DP is efficient if the numbers are small, and this is where we get the concept of weak NP-hardness – a formal kind of “easy if the numbers are small,” if you will.

The quick version is this: amend the idea of “reasonable encoding” to say that encoding numbers in unary is reasonable. If the problem is still NP-hard, then the problem is called strongly NP-hard. If the problem is NP-hard in the normal way but can now be solved in polynomial time, such as is the case with Knapsack, then the problem is called weakly NP-hard. There’s a related concept called “pseudopolynomial” runtime, but I’ll let you look that up on your own.

Here are some quick points.

If the input is combinatorial (like a graph; just things), then technically the hardness will be strong. Even if there’s a number in the decision version of a problem (like: is there an independent set of size at least $k$?), the problem is often trivial (or nonsensical) when that number is large.

2-PARTITION is weakly NP-hard: can you partition this set of numbers into two groups that have equal sum? You have to watch out if you reduce from this: the hardness is weak.

3-PARTITION is strongly NP-hard: can you partition this set of numbers into groups of three that each have equal sum? (Watch out! Not three groups: groups of three.) This is hard even if the numbers are small and we’ll talk about that some other time - it’s really quite nice for reductions.