Sub-exponential time

The term sub-exponential time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon, and we list the two most widely used ones below.

First definitionedit

A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every ε > 0 there exists an algorithm which solves the problem in time O(2nε). The set of all such problems is the complexity class SUBEXP which can be defined in terms of DTIME as follows.

This notion of sub-exponential is non-uniform in terms of ε in the sense that ε is not part of the input and each ε may have its own algorithm for the problem.

Second definitionedit

Some authors define sub-exponential time as running times in 2o(n). This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the general number field sieve, which runs in time about ${\displaystyle 2^{\stackrel{~<!--\; ~\; -->}{O}(n^{1/3})}}$, where the length of the input is n. Another example is the graph isomorphism problem, where Luks's algorithm runs in time ${\displaystyle 2^{O(\sqrt{n\log <!--\; \; -->n})}}$. (In 2015–2017, Babai reduced the complexity of this problem to quasi-polynomial time.)

It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In parameterized complexity, this difference is made explicit by considering pairs ${\displaystyle (L,k)}$ of decision problems and parameters k. SUBEPT is the class of all parameterized problems that run in time sub-exponential in k and polynomial in the input size n:

${\displaystyle \text{SUBEPT}=\text{DTIME}\left(2^{o(k)}\cdot <!--\; \cdot \; -->\text{poly}(n)\right).}$

More precisely, SUBEPT is the class of all parameterized problems ${\displaystyle (L,k)}$ for which there is a computable function ${\displaystyle f:\mathbb{N}\to <!--\; \to \; -->\mathbb{N}}$ with ${\displaystyle f\in <!--\; \in \; -->o(k)}$ and an algorithm that decides L in time ${\displaystyle 2^{f(k)}\cdot <!--\; \cdot \; -->\text{poly}(n)}$.

Exponential time hypothesisedit

The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, at most, three literals per clause and with n variables, cannot be solved in time 2o(n). More precisely, the hypothesis is that there is some absolute constant c>0 such that 3SAT cannot be decided in time 2cn by any deterministic Turing machine. With m denoting the number of clauses, ETH is equivalent to the hypothesis that kSAT cannot be solved in time 2o(m) for any integer k ≥ 3. The exponential time hypothesis implies P ≠ NP.