Editing Time complexity (section)

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