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

Problem Detail: 

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}$.

Asked By : ksb

Answered By : Kaveh

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9813