Are there subexponential-time algorithms for NP-complete problems?

Question

Are there NP-complete problems which have proven subexponential-time algorithms?

I am asking for the general case inputs, I am not talking about tractable special cases here.

By sub-exponential, I mean an order of growth above polynomials, but less than exponential, for example $n^{\log n}$.

Answer 1

Depends on what you mean by subexponential. Below I explain a few meanings of "subexponential" and what happens in each case. Each of these classes is contained in the classes below it.

---

I. $2^{n^{o(1)}}$

If by subexpoential you mean $2^{n^{o(1)}}$, then a conjecture in complexity theory called ETH (Exponential Time Hypothesis) implies that no $\mathsf{NP}$-hard problem can have an algorithm with running-time $2^{n^{o(1)}}$.

Note that this class is closed under composition with polynomials. If we have a subexponential time algorithm for any $\mathsf{NP}$-hard problem, we can combine it with a polynomial-time reduction from SAT to it obtain a subexponential algorithm for 3SAT which would violate ETH.

II. $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for all $0 < \epsilon$

The situation is similar to the previous one.

It is closed under polynomials so no $\mathsf{NP}$-hard problem can be solved in this time without violating ETH.

---

III. $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for some $\epsilon < 1$

If by subexponential you mean $2^{O(n^\epsilon)}$ for some $\epsilon<1$ then the answer is yes, there are provably such problems.

Take an $\mathsf{NP}$-complete problem like SAT. It has a brute-force algorithm that runs in time $2^{O(n)}$. Now consider the padded version of SAT by adding a string of size $n^k$ to the inputs:

$$SAT' = \{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \}$$

Now this problem is $\mathsf{NP}$-hard and can be solved in time $2^{O(n^\frac{1}{k})}$.

IV. $2^{o(n)}$

This contains the previous class, the answer is similar.

V. $\bigcap_{0 < \epsilon}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for all $\epsilon>0$

This contains the previous class, the answer is similar.

VI. $\bigcup_{\epsilon < 1}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for some $\epsilon<1$

This contains the previous class, the answer is similar.

---

What does subexponential mean?

"Above polynomial" is not an upper-bound but a lower-bound and is referred to as superpolynomial.

Functions like $n^{\lg n}$ are called quasipolynomial, and as the name indicates are almost polynomial and far from being exponential, subexponential is usually used to refer a much larger class of functions with much faster growth rates.

As the name indicates, "subexponential" means slower than exponential. By exponential we usually mean functions in class $2^{\Theta(n)}$, or in the nicer class $2^{n^{\Theta(1)}}$ (which is closed under composition with polynomials).

Subexponetial should be close to these but smaller. There are different ways to do this and there is not a standard meaning. We can replace $\Theta$ by $o$ in the two definitions of exponential and obtain I and IV. The nice thing about them is that they are uniformly defined (no quantifier over $\epsilon$). We can replace $\Theta$ with a multiplicative coefficient $\epsilon$ for all $\epsilon>0$, we get II and V. Their are close to I and IV but nonuniformly defined. The last option is to replace $\Theta$ with a multiplicative constant $\epsilon$ for some $\epsilon<1$. This gives II and VI.

Which one should be called subexponential is arguable. Usually people use the one they need in their work and refer to it as subexponential.

I is my personal preference, it is a nice class: it is closed under composition with polynomials and it is uniformly defined. It is similar to $\mathsf{Exp}$ which uses $2^{n^{O(1)}}$.

II is seems to be used in the definition of the complexity class $\mathsf{SubExp}$.

III is used for algorithmic upper-bounds, like those mentioned in Pal's answer.

IV is also common.

V is used to state the ETH conjecture.

Intersections (II and V) are not that useful for algorithmic upper-bounds, their main use seems to be complexity theory. In practice, you will not see a difference between I and II or between IV and V. IMHO the later three definition (IV, V, VI) are too sensitive, they might be useful for particular problems, but they are not robust which decreases their usefulness as classes. Robustness and nice closure properties are part of the reason why famous complexity classes like $\mathsf{L}$, $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{PSpace}$, and $\mathsf{Exp}$ are interesting.

Summery

IMHO, the main definitions are I and III. We already have subexponential algorithms for $\mathsf{NP}$-hard problems in the sense of III and we cannot have them in the sense of I without violating ETH.

Answer 2

Just to list some, all with running time more or less $2^{O(\sqrt{n} \log n)}n^{O(1)}$ or $2^{O(\sqrt{n})}n^{O(1)}$:

• Feedback Arc Set on Tournaments [Noga Alon , Daniel Lokshtanov , Saket Saurabh, ALP 2009]
• Minimum Fill-in and Chain Completion [Fomin and Villanger SODA 2012]
• Split Edge Deletion [Ghosh et al SWAT 2012]
• Cluster Editing with $t$ clusters [Fomin et al STACS 2013]
• Lots of bidimensionality problems, different graph problems on bounded genus graphs and especially planar graphs (see Demaine, Fomin, Hajiaghayi, Thilikos: Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs)
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs [Pilipczuk et al STACS 2013]
• Trivially Perfect Completion, Threshold Completion and Pseudosplit Completion [D. et al STACS 2014]
• Interval Completion [Bliznets et al]
• Proper Interval Completion [Bliznets et al]