Subexponential Time Needs a Ruler

When we say that an algorithm is polynomial time, we usually measure time as a function of the input size. For 3-SAT, there are several natural sizes: the number of variables $n$, the number of clauses $m$, or the total size $n+m$.

For polynomial time, these choices lead to the same broad notion. If every variable occurs in some clause, then

$$n\le 3m.$$

Conversely, $m$ is also polynomially bounded by $n$ if we ignore duplicate clauses. Each variable $x_i$ gives two possible literals, namely $x_i$ and $\neg x_i$. So there are $2n$ possible literals in total.

A 3-clause has three literal positions. For each position there are at most $2n$ choices, so the number of possible 3-clauses is at most

$$(2n{)}^3.$$

This is only an upper bound, since it also counts repeated literals and different orderings of the same clause. That is fine here. It shows that $m$ is at most polynomial in $n$ for distinct clauses.

The polynomial world is coarse

Thus measuring by $n$, by $m$, or by $n+m$ only changes one polynomial bound into another.

For example, suppose an algorithm runs in time $n^d$ for some constant $d$. Since $n\le n+m$, the same running time is also bounded by

$$(n+m{)}^d.$$

Conversely, since $m\le (2n{)}^3$, we have

$$n+m\le n+(2n{)}^3.$$

So a polynomial in $n+m$ is still bounded by a polynomial in $n$:

$$(n+m{)}^d\le {\left(n+(2n{)}^3\right)}^d=n^{O(d)}.$$

The exponent of the polynomial may change, but the result is still polynomial time. This is the key point: for the question of whether a problem is in polynomial time, these measures are interchangeable.

This is why the P versus NP question does not need a careful discussion of whether 3-SAT is measured by variables or by clauses. Polynomial time is too coarse to notice the difference.

The exponent is the terrain

Subexponential time is different. Now the exponent itself is the object of study. The difference between

$$2^{cn},2^{c\sqrt{n}},2^{c{n}^{0.99}}$$

is exactly the difference we care about. A polynomial change in the parameter can move a bound across the line between single-exponential and subexponential.

That is the small trap behind the exponential time hypothesis. It wants to say that 3-SAT has no subexponential algorithm, but it must first decide what the parameter is.

One possible statement uses the number of variables:

$$\text{3-SAT has no }{O}^{\ast }(2^{o(n)})\text{ algorithm.}$$

Another uses the number of clauses $m$. A third uses the total size $n+m$. At first sight these look like slightly different hypotheses.

The good news is that this ambiguity disappears. Impagliazzo, Paturi, and Zane showed that the natural formulations using $n$, using $m$, and using $n+m$ are equivalent. So ETH is not an artefact of choosing the wrong measure.

In the usual form, ETH says:

$$\text{3-SAT cannot be solved in }{O}^{\ast }(2^{o(n)})\text{ time.}$$

Here $n$ is the number of variables, and O-star notation hides polynomial factors.

A stronger kind of hardness

ETH is stronger than $P\ne NP$ because it forbids a larger range of possible running times for 3-SAT.

The statement $P\ne NP$ only rules out the first zone. It says that 3-SAT has no polynomial-time algorithm, so it forbids running times such as

$$(n+m{)}^{10}\text{or}(n+m{)}^{1000}.$$

But it says nothing about algorithms that are slower than every polynomial and still much faster than $2^{cn}$. For example, $P\ne NP$ is still compatible with a 3-SAT algorithm running in time

$$2^{100n^{0.9}}(n+m{)}^{50}.$$

This time bound is not polynomial, because of the exponential term $2^{100n^{0.9}}$. So it would not contradict $P\ne NP$.

But it is subexponential in $n$, because

$$100n^{0.9}=o(n).$$

So the same algorithm would contradict ETH. This is the middle zone: not polynomial, but still subexponential.

Thus $P\ne NP$ says: no polynomial algorithm for 3-SAT. ETH says: no polynomial algorithm and no subexponential non-polynomial algorithm for 3-SAT. That is why ETH forbids more algorithms.

This gives ETH its role in exact algorithms. It says that some improvements over brute force are meaningful, but that a subexponential algorithm for 3-SAT would be a major collapse of our current picture.

Geometry changes the search

Planar graph problems show the other side of the story. Planar vertex cover, planar independent set, and planar dominating set remain hard in the usual NP-complete sense, but they admit algorithms of the form

$$2^{O(\sqrt{n})}.$$

The point is not that planarity makes these problems easy. They are still NP-complete. The point is that planarity gives the graph a shape. A planar graph has a small separator: a set of only $O(\sqrt{n})$ vertices whose removal breaks the graph into smaller components.

This boundary is where the hard global interaction is concentrated. If we know what happens on the separator, then the two sides no longer need to coordinate with each other directly. They only need to agree with the fixed boundary choice.

Vertex Cover

For a problem such as vertex cover, the boundary choice says which separator vertices are selected. There are only

$$2^{|S|}=2^{O(\sqrt{n})}$$

such choices.

Colouring

For colouring problems, each separator vertex may have three possible colours, so the boundary has up to

$$3^{|S|}$$

states. This still has the same subexponential shape. Since

$$3^{|S|}=2^{|S|{\log }_{2}3},$$

and ${\log }_{2}3$ is just a constant, a separator of size $|S|=O(\sqrt{n})$ gives

$$3^{|S|}=2^{O(\sqrt{n})}.$$

The important quantity is therefore not the exact constant base, but the number of separator vertices in the exponent.

After one boundary choice is fixed, the graph falls into pieces. The left piece and the right piece can be solved independently, because every path between them had to pass through the separator. This is the algorithmic value of the separator: it turns one large search into a boundary search plus two smaller searches.

Recursing gives a subexponential running time. At the top level we pay $2^{O(\sqrt{n})}$ for the separator choices. The subproblems are smaller, and the same separator idea applies again at every recursive level.

Thus a piece of size at most $\alpha n$ gets a separator of size $O(\sqrt{\alpha n})$, and a piece of size at most ${\alpha }^{2}n$ gets a separator of size $O(\sqrt{{\alpha }^{2}n})$. The separator cost shrinks with the subproblem size.

The resulting recurrence has the shape

$$T(n)\le 2^{O(\sqrt{n})}(T(n_1)+T(n_2)),n_1,n_2\le \alpha n$$

Here $\alpha$ is a fixed shrink factor from the separator theorem. For example, one may think of $\alpha =2/3$: after removing the separator, each recursive piece has at most a constant fraction of the original vertices. The exact value is not important; what matters is that $\alpha <1$. This resolves to

$$T(n)=2^{O(\sqrt{n})}.$$

Now apply this shrink repeatedly. The root problem has size $n$. Its children have size at most $\alpha n$. Their children have size at most ${\alpha }^{2}n$, and so on. Since $\alpha <1$, the separator sizes also shrink at each level.

So there are two lessons at once. Geometry can make some NP-complete problems subexponential by exposing small boundaries. ETH says that we should not expect the same miracle for 3-SAT itself, where no such planar separator structure is present.