EXPTIME Complexity Class

Context

Wikipedia2026 - EXPTIME seeds the wiki’s reusable reference for deterministic exponential time. This annex keeps the class definition, containment facts, and hardness vocabulary in one place so EXPTIME can stay concept-level and formal-methods notes can link to the technical anchor when needed.

Formal Statement

EXPTIME is the class of decision problems decidable by a deterministic Turing machine in exponential time:

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

Equivalently, a language is in EXPTIME when it is decidable in time O(2^{p(n)}) for some polynomial p.

A standard containment chain is:

$$\mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{PSPACE}\subseteq \mathrm{EXPTIME}\subseteq \mathrm{NEXPTIME}\subseteq \mathrm{EXPSPACE}.$$

The time hierarchy theorem gives the strict separation:

$$\mathrm{P}⊊\mathrm{EXPTIME}.$$

The alternation characterization is:

$$\mathrm{EXPTIME}=\mathrm{APSPACE},$$

where APSPACE is polynomial-space computation by an alternating Turing machine.

Derivation / Construction

The union definition allows the exponent to grow as any fixed polynomial in the input size. This is why both 2^n and 2^{n^3}-time deterministic decision procedures live in EXPTIME, while the class remains below deterministic exponential space.

The inclusion PSPACE \subseteq EXPTIME follows from the finite configuration graph of a polynomial-space computation: with only exponentially many configurations, exhaustive reachability-style simulation gives an exponential-time upper bound.

The equality EXPTIME = APSPACE connects deterministic exponential time to alternating polynomial-space search. In formal-methods settings, this matters because game-like or branching proof searches often have natural alternating-machine interpretations.

An EXPTIME-hard problem is one to which every problem in EXPTIME reduces under the chosen reduction notion, usually polynomial-time many-one reductions. An EXPTIME-complete problem is both in EXPTIME and EXPTIME-hard.

Implications

• An EXPTIME upper bound says exact decision is possible, but worst-case scaling is severe.
• EXPTIME-completeness is a warning about unrestricted exact reasoning, not a claim that every structured practical instance is hopeless.
• Verification, synthesis, planning, and game-solving notes should surface EXPTIME when it changes the interpretation of tractability claims.

Links

• EXPTIME
• Wikipedia2026 - EXPTIME
• Formal Methods
• Algorithms and Data Structures