In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable...

In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic...

algorithms belong to the complexity class 2-EXPTIME. 2-EXPTIME = ⋃ c ∈ N DTIME ( 2 2 n c ) {\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N}...

complexity classes relate to each other in the following way: L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME⊆EXPSPACE (where ⊆ denotes the subset relation). However, many...

polynomial function of n. A decision problem is EXPTIME-complete if it is in EXPTIME, and every problem in EXPTIME has a polynomial-time many-one reduction to...

and is a superset of EXPSPACE. An example of a problem in 2-EXPTIME that is not in EXPTIME is the problem of proving or disproving statements in Presburger...

original (PDF) on 2016-04-03. J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018...

EXPTIME-complete EXPTIME-complete undecidable EXPTIME-complete undecidable undecidable coBüchi undecidable EXPTIME-complete EXPTIME-complete EXPTIME-complete...

{\mathsf {NP}}\subseteq {\mathsf {PSPACE}}\subseteq {\mathsf {EXPTIME}}.} Here, EXPTIME is the class of problems solvable in exponential time. Of all...

player in a given position is EXPTIME-complete. Generalized chess, go (with Japanese ko rules), Quixo, and checkers are EXPTIME-complete. Game complexity...