patternCritical
Are there subexponential-time algorithms for NP-complete problems?
Viewed 0 times
areproblemstimealgorithmscompleteforsubexponentialthere
Problem
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}$.
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}$.
Solution
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 0$
This contains the previous class, the answer is similar.
VI. $\bigcup_{\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.
Summary
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.
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 0$
This contains the previous class, the answer is similar.
VI. $\bigcup_{\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.
Summary
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.
Context
StackExchange Computer Science Q#9813, answer score: 73
Revisions (0)
No revisions yet.