2-EXPTIME

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(2^{2^p(n)}) time, where p(n) is a polynomial function of n.

In terms of DTIME,

: $\mathsf{2\mbox{-}EXPTIME} = \bigcup_{k \in \mathbb{N} } \mathsf{ DTIME } \left( 2^{ 2^{n^k} } \right) .$

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), {{isbn|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 $2^{2^{2^{n^k}}}$ . 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, "[http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps "Super-Exponential Complexity of Presburger Arithmetic.] {{Webarchive|url=https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps |date=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.{{cite journal |last1=Dubé |first1=Thomas W. |title=The Structure of Polynomial Ideals and Gröbner Bases |journal=SIAM Journal on Computing |date=August 1990 |volume=19 |issue=4 |pages=750–773 |doi=10.1137/0219053}}
Finding a complete set of associative-commutative unifiers{{citation

| last1 = Kapur | first1 = Deepak

| last2 = Narendran | first2 = Paliath

| title = [1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science

| contribution = Double-exponential complexity of computing a complete set of AC-unifiers

| doi = 10.1109/LICS.1992.185515

| pages = 11–21

| url = http://citeseer.ist.psu.edu/337363.html

| year = 1992

| isbn = 0-8186-2735-2| s2cid = 206437926

}}.

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.{{Cite journal |last=Ben-Or |first=Michael |last2=Kozen |first2=Dexter |last3=Reif |first3=John |date=1986-04-01 |title=The complexity of elementary algebra and geometry |url=https://www.sciencedirect.com/science/article/pii/0022000086900292 |journal=Journal of Computer and System Sciences |volume=32 |issue=2 |pages=251–264 |doi=10.1016/0022-0000(86)90029-2 |issn=0022-0000}}
Calculating the complement of a regular expression{{cite conference

| last1 = Gruber | first1 = Hermann

| last2 = Holzer | first2 = Markus

| title = Finite Automata, Digraph Connectivity, and Regular Expression Size

| pages = 39–50

| book-title = Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008)

| url = http://www.hermann-gruber.com/data/icalp08.pdf

| year = 2008

| doi = 10.1007/978-3-540-70583-3_4

| volume = 5126

}}

2-EXPTIME-complete problems

= Logic =

The satisfiability problem for CTL⁺ (Computation tree logic) is 2-EXPTIME-complete.{{citation |last1=Johannsen |first1=Jan |title=Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) |volume=2719 |pages=767–775 |year=2003 |editor1-last=Baeten |editor1-first=Jos C. M. |url=http://www.tcs.informatik.uni-muenchen.de/~mlange/papers/icalp03.pdf |access-date=2006-12-22 |archive-url=https://web.archive.org/web/20070930220755/http://www.tcs.informatik.uni-muenchen.de/~mlange/papers/icalp03.pdf |archive-date=2007-09-30 |url-status=dead |series=Lecture Notes in Computer Science |contribution=CTL⁺ is complete for double exponential time |publisher=Springer-Verlag |doi=10.1007/3-540-45061-0_60 |isbn=978-3-540-40493-4 |last2=Lange |first2=Martin |editor2-last=Lenstra |editor2-first=Jan Karel |editor3-last=Parrow |editor3-first=Joachim |editor4-last=Woeginger |editor4-first=Gerhard J. |editor2-link=Jan Karel Lenstra |editor4-link=Gerhard J. Woeginger}}. The satisfiability problem of ATL* (alternating-time temporal logic) is 2-EXPTIME-complete.{{Cite journal |last=Schewe |first=Sven |date=2008 |editor-last=Aceto |editor-first=Luca |editor2-last=Damgård |editor2-first=Ivan |editor3-last=Goldberg |editor3-first=Leslie Ann |editor4-last=Halldórsson |editor4-first=Magnús M. |editor5-last=Ingólfsdóttir |editor5-first=Anna |editor6-last=Walukiewicz |editor6-first=Igor |title=ATL* Satisfiability Is 2EXPTIME-Complete |url=https://link.springer.com/chapter/10.1007/978-3-540-70583-3_31 |journal=Automata, Languages and Programming |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=373–385 |doi=10.1007/978-3-540-70583-3_31 |isbn=978-3-540-70583-3}}

Implicational Relevance Logic is 2-EXPTIME-complete.{{Cite journal |last=Schmitz |first=Sylvain |date=2016 |title=Implicational Relevance Logic Is 2-Exptime-Complete |url=https://www.jstor.org/stable/43864316 |journal=The Journal of Symbolic Logic |volume=81 |issue=2 |pages=641–661 |issn=0022-4812}}

The satisfiability problem for propositional dynamic logic with intersection (IPDL) is 2-EXPTIME-complete.{{Cite journal |last=Lange |first=Martin |last2=Lutz |first2=Carsten |date=2005 |title=2-Exptime Lower Bounds for Propositional Dynamic Logics with Intersection |url=https://www.jstor.org/stable/27588414 |journal=The Journal of Symbolic Logic |volume=70 |issue=4 |pages=1072–1086 |issn=0022-4812}}

= 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.{{cite journal | author = Jussi Rintanen | title = Complexity of Planning with Partial Observability | journal = Proceedings of International Conference on Automated Planning and Scheduling | publisher = AAAI Press | pages = 345–354 | year = 2004 | url=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 2EXPTIME-complete.{{Cite journal |last=Pnueli |first=A. |last2=Rosner |first2=R. |date=1989-01-03 |title=On the synthesis of a reactive module |url=https://dl.acm.org/doi/10.1145/75277.75293 |journal=Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages |series=POPL '89 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=179–190 |doi=10.1145/75277.75293 |isbn=978-0-89791-294-5}}

References

Category:Complexity classes