Some NP-Complete Problems Fit Through Subexponential Gaps

The usual story around NP-complete problems is that we do not expect polynomial-time algorithms. But that still leaves a lot of room between polynomial time and the trivial exhaustive search bound.

For many exact algorithms, progress means shaving the exponential base. For 3-SAT, the naive bound

can be improved by more careful branching to a single-exponential bound with a smaller base, such as

Later algorithms improve this further. These are still exponential, but less brutal.

This is still called single-exponential time. In this context, single-exponential means the running time has the form

For example,

Even base is still single-exponential, because changing the constant base only changes the constant hidden inside .

A sharper question is whether an NP-complete problem can be solved in subexponential time, meaning time strictly better than in the exponent, such as . Toy examples show that the answer can be yes if the input is restricted in the right way.

Consider a variant of vertex cover where the input graph on vertices is promised to contain at most edges. Call it sparse vertex cover. It is still NP-complete: membership in NP is inherited from vertex cover, and any vertex-cover instance can be padded with isolated vertices until the number of vertices is large enough that the edge bound holds.

But the padded problem has a subexponential algorithm in terms of the padded input size. Only vertices incident to edges matter. With at most edges, there are at most non-isolated vertices. All other vertices can be ignored.

Trying all subsets of the active vertices takes at most

which is subexponential in .

This example is artificial. It gets subexponential time by padding the input with irrelevant isolated vertices. The more interesting question is whether natural NP-complete problems have subexponential algorithms. That depends on the problem and on what parameter is used as the input size. The point is that NP-completeness alone does not tell us the exact exponential scale.