Editing Time complexity (section)

== {{anchor|subexponential time}}Sub-exponential time ==
The term '''[[Infra-exponential|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,<ref>{{Cite web|url=http://scottaaronson.com/blog/?p=394 |title=A not-quite-exponential dilemma |author=Aaronson, Scott |date=5 April 2009 |work=Shtetl-Optimized |access-date=2 December 2009}}</ref> however the two most widely used are below.

===First definition===
<!-- [[SUBEXP]] redirects here -->

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 {{nowrap|''ε'' > 0}} there exists an algorithm which solves the problem in time ''O''(2<sup>''n''<sup>''ε''</sup></sup>). The set of all such problems is the complexity class '''SUBEXP''' which can be defined in terms of [[DTIME]] as follows.<ref name="bpp">{{Cite journal| last1=Babai | first1=László | author1-link = László Babai | last2=Fortnow | first2=Lance | author2-link = Lance Fortnow | last3=Nisan | first3=N. | author3-link = Noam Nisan | last4=Wigderson | first4=Avi | author4-link = Avi Wigderson | title=BPP has subexponential time simulations unless EXPTIME has publishable proofs | publisher=[[Springer-Verlag]] | location=Berlin, New York | year=1993 | journal=Computational Complexity | volume=3 | issue=4 | pages=307–318 | doi=10.1007/BF01275486| s2cid=14802332 }}</ref><ref>{{ComplexityZoo|Class SUBEXP: Deterministic Subexponential-Time|S#subexp}}</ref><ref>{{Cite conference| last1=Moser | first1=P. | contribution=Baire's Categories on Small Complexity Classes | publisher=Springer-Verlag | location=Berlin, New York | year=2003 | series=[[Lecture Notes in Computer Science]] |editor1=Andrzej Lingas |editor2=Bengt J. Nilsson|title=Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings| volume=2751 | issn=0302-9743 | pages=333–342| doi=10.1007/978-3-540-45077-1_31 | isbn=978-3-540-40543-6 }}</ref><ref>{{Cite book| last1=Miltersen | first1=P.B. | chapter=Derandomizing Complexity Classes | title=Handbook of Randomized Computing | publisher=Kluwer Academic Pub | year=2001 | volume=9 | page=843| doi=10.1007/978-1-4615-0013-1_19 | series=Combinatorial Optimization | doi-broken-date=1 November 2024 | isbn=978-1-4613-4886-3 }}</ref>

:<math>\textsf{SUBEXP}=\bigcap_{\varepsilon>0} \textsf{DTIME}\left(2^{n^\varepsilon}\right)</math>

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 definition ===
Some authors define sub-exponential time as running times in <math>2^{o(n)}</math>.<ref name="ETH" /><ref>{{Cite journal| last1=Kuperberg | first1=Greg | title=A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem | location=Philadelphia | year=2005 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=35 | issue=1 | page=188 | doi=10.1137/s0097539703436345| arxiv=quant-ph/0302112 | s2cid=15965140 }}</ref><ref>{{cite arXiv|eprint=quant-ph/0406151v1|author1=Oded Regev|title=A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space|year=2004}}</ref> 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 {{nowrap|<math>2^{\tilde{O}(n^{1/3})}</math>,}} where the length of the input is {{mvar|n}}. Another example was the [[graph isomorphism problem]], which the best known algorithm from 1982 to 2016 solved in {{nowrap|<math>2^{O\left(\sqrt{n \log n}\right)}</math>.}} However, at [[Symposium on Theory of Computing|STOC]] 2016 a quasi-polynomial time algorithm was presented.<ref>{{cite book
 | last1 = Grohe | first1 = Martin
 | last2 = Neuen | first2 = Daniel
 | editor1-last = Dabrowski | editor1-first = Konrad K.
 | editor2-last = Gadouleau | editor2-first = Maximilien
 | editor3-last = Georgiou | editor3-first = Nicholas
 | editor4-last = Johnson | editor4-first = Matthew
 | editor5-last = Mertzios | editor5-first = George B.
 | editor6-last = Paulusma | editor6-first = Daniël
 | arxiv = 2011.01366
 | contribution = Recent advances on the graph isomorphism problem
 | isbn = 978-1-009-01888-3
 | mr = 4273431
 | pages = 187–234
 | publisher = Cambridge University Press
 | series = London Mathematical Society Lecture Note Series
 | title = Surveys in combinatorics 2021
 | volume = 470
 | year = 2021}}</ref>

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 <math>(L,k)</math> of [[decision problem]]s 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'':<ref>{{Cite book
 | last1=Flum   | first1=Jörg
 | last2=Grohe | first2=Martin | author2-link = Martin Grohe
 | title = Parameterized Complexity Theory | year = 2006 | publisher = Springer
 | url = https://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
 | isbn = 978-3-540-29952-3 | page=417}}</ref>

:<math>\textsf{SUBEPT}=\textsf{DTIME}\left(2^{o(k)} \cdot \textsf{poly}(n)\right).</math>

More precisely, SUBEPT is the class of all parameterized problems <math>(L,k)</math> for which there is a [[computable function]] <math>f : \N \to \N</math> with <math>f \in o(k)</math> and an algorithm that decides ''L'' in time <math>2^{f(k)} \cdot \textsf{poly}(n)</math>.

==== Exponential time hypothesis ====
{{Main|Exponential time hypothesis}}

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 2<sup>''o''(''n'')</sup>. More precisely, the hypothesis is that there is some absolute constant {{math|''c'' > 0}} such that 3SAT cannot be decided in time 2<sup>''cn''</sup> by any deterministic Turing machine. With ''m'' denoting the number of clauses, ETH is equivalent to the hypothesis that ''k''SAT cannot be solved in time 2<sup>''o''(''m'')</sup> for any integer {{math|''k'' ≥ 3}}.<ref>{{Cite journal|first1=R.|last1=Impagliazzo|author1-link=Russell Impagliazzo|first2=R.|last2=Paturi|first3=F.|last3=Zane|title=Which problems have strongly exponential complexity?|journal=[[Journal of Computer and System Sciences]]|volume=63|issue=4|year=2001|pages=512–530|doi=10.1006/jcss.2001.1774|doi-access=free}}</ref> The exponential time hypothesis implies [[P ≠ NP]].