Editing Time complexity (section)

=== 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]].