 |
It has been suggested that this article or section be merged into Time complexity. (Discuss) |
In computational complexity theory, sub-exponential time refers to a running time that is a sub-exponential function of the input size. Sub-exponential time algorithms are those that run in time greater than polynomial time ("super-polynomial time"), but less than exponential time. Sub-exponential time algorithms are considered to be computationally infeasible for larger inputs.
An algorithm whose input is of length n is sub-exponential time if its worst-case running time is 
for all ε > 0. In other words, for every ε > 0 there exists an algorithm which solves the problem in time . The algorithm for each ε can depend on ε. More formally, we define the complexity class SUBEXP of all problems which admit sub-exponential time algorithms in terms of DTIME as follows.[1][2][3][4]
However, some authors define sub-exponential time as any running time that is less than O(2cn) for all c. By this definition, an algorithm whose input is of length n is sub-exponential time if its worst-case running time is 2o(n).[5][6][7] This definition includes more functions than the previous 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 
, where the length of the input is n. Another example is the best-known algorithm for the graph isomorphism problem, which runs in time 2O(√(n log n)). The fact that "sub-exponential time" is often used to mean two different things has also been discussed.[8]
Contents |
Quasi-polynomial time
An important subclass of sub-exponential time algorithms are quasi-polynomial time algorithms. The worst case running time of a quasi-polynomial time algorithm is 
for some fixed c. The factoring algorithm described above is not quasi-polynomial since the running time, where n is the input size, is 
. If the constant "c" in the definition of quasi-polynomial time algorithms is equal to 1, we get a polynomial time algorithm, and if it less than 1, we get a sub-polynomial time algorithm.
Quasi-polynomial time algorithms typically arise in reductions from an NP-hard problem to another problem. For example, one can take an instance of an NP hard problem, say 3SAT, and convert it to an instance of another problem B, but the size of the instance becomes . In that case, this reduction does not prove that problem B is NP-hard; this reduction only shows that there is no polynomial time algorithm for B unless there is a quasi-polynomial time algorithm for 3SAT (and thus all of NP). Similarly, there are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed Steiner tree problem problem, for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of O(log2n) (n being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.
The complexity class QP consists of all problems which have quasi-polynomial time algorithms. It can be defined in terms of DTIME as follows.[9]
The following table summarises some classes of running times that lie between polynomial and exponential running times. In the table, poly(x) = xO(1), i.e., polynomial in x. See big O notation for more examples.
| Name | Complexity class | Running time | Examples of running times |
|---|---|---|---|
| polynomial time | P | 2O(log n) = poly(n) | n, n log n, n10 |
| quasi-polynomial time | QP | 2poly(log n) | nlog log n, nlog n |
| sub-exponential time (first definition) | SUBEXP | O(2nε) for all ε > 0 | |
| sub-exponential time (second definition) | 2o(n) | 2n1/3 | |
| exponential time | E | 2O(n) | 1.1n, 10n |
| exponential time | EXPTIME | 2poly(n) | n!, nn, 2n2 |
Relation to NP-complete problems
In complexity theory, the P versus NP problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for NP-complete problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented above. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the exponential time hypothesis.[5] Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of approximation algorithms make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the set cover problem.
See also
References
- ^ Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time
- ^ Moser, P. (2003), "Baire's Categories on Small Complexity Classes", Lecture Notes in Computer Science (Berlin, New York: Springer-Verlag): 333–342, ISSN 0302-9743
- ^ Miltersen, P.B. (2001), "DERANDOMIZING COMPLEXITY CLASSES", Handbook of Randomized Computing (Kluwer Academic Pub): 843
- ^ Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993), "BPP has subexponential time simulations unless EXPTIME has publishable proofs", Computational Complexity (Berlin, New York: Springer-Verlag) 3 (4): 307–318, doi:
- ^ a b Impagliazzo, R.; Paturi, R. (2001), "On the complexity of k-SAT", Journal of Computer and System Sciences (Elsevier) 62 (2): 367–375, doi:, ISSN 1090-2724
- ^ Kuperberg, Greg (2005), "A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 35 (1): 188, ISSN 1095-7111
- ^ Oded Regev (2004). "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space". arΧiv:quant-ph/0406151v1 [quant-ph].
- ^ Aaronson, Scott (5 April 2009), "A not-quite-exponential dilemma", Shtetl-Optimized, http://scottaaronson.com/blog/?p=394, retrieved 2 December 2009
- ^ Complexity Zoo: Class QP: Quasipolynomial-Time
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
