EXPTIME

Definition

EXPTIME is the class of decision problems solvable by a deterministic Turing machine in exponential time. A standard definition is

$$\mathrm{EXPTIME}=\bigcup _{k\ge 1}\mathrm{DTIME}(2^{n^k}),$$

equivalently the set of problems decidable in time O(2^{p(n)}) for some polynomial p.

Why It Matters

It is a coarse but important marker of worst-case difficulty. When a verification, synthesis, planning, or game-solving problem lands in EXPTIME, exact reasoning is still decidable, but the asymptotic cost is often high enough that structure, abstraction, or restricted problem classes become central.

Formalism / Key Objects

• Deterministic exponential time: \mathrm{DTIME}(2^{p(n)}) for polynomial p.
• Inclusion chain: \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME} \subseteq \mathrm{NEXPTIME} \subseteq \mathrm{EXPSPACE}.
• Strict separation: the time hierarchy theorem gives \mathrm{P} \subsetneq \mathrm{EXPTIME}.
• Alternation characterization: \mathrm{EXPTIME} = \mathrm{APSPACE}.
• Hardness signal: an EXPTIME-complete problem is among the hardest problems known in the class under standard polynomial-time reductions.
• EXPTIME Complexity Class collects the reusable class definition, containment facts, and hardness vocabulary.

Connections

• Relevant to Formal Methods because model checking, synthesis, and logical reasoning procedures are often compared by whether their worst-case bounds stay in polynomial, PSPACE, or EXPTIME territory.
• Connects to Situation Calculus and related action formalisms when richer expressivity leads to harder executability or planning questions.
• Connects to Invariant Synthesis because strategy synthesis and game-solving pipelines are often evaluated partly through the complexity class of the exact decision problem.
• Artale2023 - Complexity of Safety and coSafety Fragments of Linear Temporal Logic shows that realizability for expressively related safety/co-safety LTL fragments can land in EXPTIME or 2EXPTIME depending on syntax and trace semantics.
• Lives under Algorithms and Data Structures as part of the wiki’s reusable complexity and tractability vocabulary.
• EXPTIME Complexity Class is the focused formal annex for the definition and containment chain.

Common Confusions

• EXPTIME is an upper-bound class, not a claim that every practical instance is infeasible.
• EXPTIME and EXPSPACE are different: one bounds time, the other bounds memory.
• EXPTIME-complete means hardest-known within EXPTIME; it does not mean every exponential-time algorithm solves an EXPTIME-complete problem.
• Exponential worst-case complexity can coexist with useful practical heuristics or highly structured tractable subclasses.

Key Sources

• Wikipedia2026 - EXPTIME
• Artale2023 - Complexity of Safety and coSafety Fragments of Linear Temporal Logic