Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

migrated from cstheory.stackexchange.com Feb 15 '13 at 16:28

This question came from our site for theoretical computer scientists and researchers in related fields.

9  
What do you mean by "sub-exponential"? If you mean $2^{o(n)}$, the answer is definitely yes. If you mean $2^{n^{o(1)}}$, I believe the answer is no. –  JeffE Feb 15 '13 at 16:40

2 Answers 2

up vote 35 down vote accepted

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.

share|improve this answer
    
This answer should go to Wikipedia. –  Erel Segal Halevi Dec 31 '13 at 17:10

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)}$:

share|improve this answer
1  
Note: these algorithms are subexponential time in the sense that they run in $2^{O(n^\epsilon)}$ time (for some $\epsilon<1$), but not in the sense that they run in time $2^{n^{o(1)}}$. –  Kaveh Apr 4 '13 at 23:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.