2-EXPTIME

Complexity class In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP, sometimes also written 2EXPTIME) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, Comparison with other complexity classes We know P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY. 2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an alternating Turing machine in exponential space. This is one way to see that EXPSPACE ⊆ 2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.Christos Papadimitriou, Computational Complexity (1994), 978-0-201-53082-7. Section 20.1, corollary 3, page 495. 2-EXPTIME is one class in a hierarchy of complexity classes with increasingly higher time bounds. The class 3-EXPTIME is defined similarly to 2-EXPTIME but with a triply exponential time bound . This can be generalized to higher and higher time bounds. Examples Examples of algorithms that require at least double-exponential time include: Each decision procedure for Presburger arithmetic provably requires at least doubly exponential timeFischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic. https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps 2006-09-15 " Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41 Computing a Gröbner basis over a field. In the worst case, a Gröbner basis may have a number of elements which is doubly exponential in the number of variables. On the other hand, the worst-case complexity of Gröbner basis algorithms is doubly exponential in the number of variables as well as in the entry size.Dubé Thomas W. The Structure of Polynomial Ideals and Gröbner Bases SIAM Journal on Computing August 1990 19 4 750–773 10.1137/0219053 Finding a complete set of associative-commutative unifiers Kapur Deepak Narendran Paliath [1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science Double-exponential complexity of computing a complete set of AC-unifiers 10.1109/LICS.1992.185515 11–21 http://citeseer.ist.psu.edu/337363.html 1992 0-8186-2735-2 206437926 subscription . Quantifier elimination on real closed fields takes doubly exponential time (see Cylindrical algebraic decomposition). Thus, deciding whether a first-order formula over the real numbers is in 2-EXPTIME. But it was shown to be EXPSPACE and was conjectured to be EXPSPACE-complete in 1986.Ben-Or Michael Kozen Dexter Reif John 1986-04-01 The complexity of elementary algebra and geometry https://dx.doi.org/10.1016/0022-0000%2886%2990029-2 Journal of Computer and System Sciences 32 2 251–264 10.1016/0022-0000(86)90029-2 0022-0000 subscription Calculating the complement of a regular expression Gruber Hermann Holzer Markus Finite Automata, Digraph Connectivity, and Regular Expression Size 39–50 Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008) https://www.researchgate.net/publication/220898363_Finite_Automata_Digraph_Connectivity_and_Regular_Expression_Size 2008 10.1007/978-3-540-70583-3_4 5126 2-EXPTIME-complete problems Logic The satisfiability problem for CTL+ (computation tree logic) is 2-EXPTIME-complete.Johannsen Jan Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) 2719 767–775 2003 Baeten Jos C. M. http://www.tcs.informatik.uni-muenchen.de/~mlange/papers/icalp03.pdf 2006-12-22 https://web.archive.org/web/20070930220755/http://www.tcs.informatik.uni-muenchen.de/~mlange/papers/icalp03.pdf 2007-09-30 dead Lecture Notes in Computer Science CTL+ is complete for double exponential time Springer-Verlag 10.1007/3-540-45061-0_60 978-3-540-40493-4 Lange Martin Lenstra Jan Karel Parrow Joachim Woeginger Gerhard J. Jan Karel Lenstra Gerhard J. Woeginger. The satisfiability problem of ATL* (alternating-time temporal logic) is 2-EXPTIME-complete.Schewe Sven ATL* Satisfiability is 2EXPTIME-Complete Lecture Notes in Computer Science 2008 5126 Aceto Luca Damgård Ivan Goldberg Leslie Ann Halldórsson Magnús M. Ingólfsdóttir Anna Walukiewicz Igor Automata, Languages and Programming https://link.springer.com/chapter/10.1007/978-3-540-70583-3_31 en Berlin, Heidelberg Springer 373–385 10.1007/978-3-540-70583-3_31 978-3-540-70583-3 Implicational Relevance Logic is 2-EXPTIME-complete.Schmitz Sylvain 2016 Implicational Relevance Logic Is 2-Exptime-Complete https://www.jstor.org/stable/43864316 The Journal of Symbolic Logic 81 2 641–661 10.1017/jsl.2015.7 43864316 1402.0705 0022-4812 The satisfiability problem for propositional dynamic logic with intersection (IPDL) is 2-EXPTIME-complete.Lange Martin Lutz Carsten 2005 2-Exptime Lower Bounds for Propositional Dynamic Logics with Intersection https://www.jstor.org/stable/27588414 The Journal of Symbolic Logic 70 4 1072–1086 10.2178/jsl/1129642115 27588414 0022-4812 subscription Planning Generalizations of many fully observable games are EXPTIME-complete. These games can be viewed as particular instances of a class of transition systems defined in terms of a set of state variables and actions/events that change the values of the state variables, together with the question of whether a winning strategy exists. A generalization of this class of fully observable problems to partially observable problems lifts the complexity from EXPTIME-complete to 2-EXPTIME-complete. Jussi Rintanen Complexity of Planning with Partial Observability Proceedings of International Conference on Automated Planning and Scheduling AAAI Press 345–354 2004 http://www.informatik.uni-freiburg.de/~ki/papers/Rintanen03compl.pdf Synthesis LTL (linear temporal logic) synthesis (deciding whether a reactive module satisfying an LTL specification) is 2-EXPTIME-complete.Pnueli A. Rosner R. On the synthesis of a reactive module 1989-01-03 Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 https://dl.acm.org/doi/10.1145/75277.75293 New York, NY, USA Association for Computing Machinery 179–190 10.1145/75277.75293 978-0-89791-294-5 Best-effort synthesis for an LTL specification is also 2-EXPTIME-complete.Aminof Benjamin De Giacomo Giuseppe Rubin Sasha 2021 Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up https://www.ijcai.org/proceedings/2021/243 Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21) 1766–1772 10.24963/ijcai.2021/243 1045-0823 11573/1575268 free See also Double exponential function References Category:Complexity classes