EXPTIME is the class of decision problems solvable by a deterministic algorithm in time , where is the input length and is a polynomial. Also written EXP, it is a central class in computational complexity theory. It includes all problems solvable in polynomial time and many problems involving exhaustive exploration of exponentially large state spaces. Membership in EXPTIME is an upper bound on computational resources, not a claim that every problem in the class requires exponential time.
Formal definition
Let denote the class of languages decided by a deterministic Turing machine in steps on inputs of length . Then
A language is a set of finite strings; deciding a language means answering whether a given input belongs to that set. The machine must halt and answer correctly on every input.
The union over all fixed positive integers is essential. EXPTIME includes time bounds such as
and bounds such as , whose polynomial factor can be absorbed into a larger exponential bound. It does not, by definition, encompass arbitrary computable running times: a bound such as lies beyond the bounds used to define EXPTIME.
The class is robust under standard changes between deterministic machine models that simulate one another with polynomial overhead. Raising to a fixed power still yields an exponential in a polynomial.
Input length and encoding
As with other time complexity classes, the relevant variable is the length of the encoded input, not necessarily the numerical value of an input parameter.
For example, an integer written in binary requires approximately bits. An algorithm taking steps can therefore take exponential time in the length of that representation. If is written in unary, the same step bound is linear in the representation length.
Standard encodings that can be translated into one another in polynomial time preserve EXPTIME membership. Succinct encodings, which may compress an exponentially large object into a short description, can change a problem’s complexity substantially.
Relationships with other complexity classes
The standard inclusions are
Here:
- P consists of problems decidable deterministically in polynomial time.
- NP consists of problems whose yes-instances have polynomial-length certificates verifiable in polynomial time.
- PSPACE consists of problems decidable using polynomial working space.
- NEXPTIME consists of problems decidable by nondeterministic machines in exponential time.
The inclusion follows from counting machine configurations. A deterministic machine using polynomial space has at most exponentially many configurations on a fixed input. If a halting computation repeated a configuration, determinism would force it into a loop. A polynomial-space decider therefore halts within an exponential number of steps.
Proven separations and open questions
The deterministic time hierarchy theorem establishes
Thus, some problems are provably solvable in deterministic exponential time but not in deterministic polynomial time. This is an unconditional theorem, unlike the unresolved P versus NP problem.
However, the following equalities remain unresolved:
In particular, the known strict separation between P and EXPTIME does not identify which inclusion in the intervening chain is strict.
EXPTIME versus E and double-exponential time
The class E is defined by
E permits an exponent linear in input length, whereas EXPTIME permits any fixed polynomial exponent. A running-time bound such as is therefore an EXPTIME bound but not an E bound. An algorithm with that running time does not, by itself, establish that its problem lies outside E: a faster algorithm might exist.
At a larger scale, 2-EXPTIME permits doubly exponential bounds of the form . The time hierarchy theorem also separates EXPTIME from 2-EXPTIME.
EXPTIME-completeness
A problem is EXPTIME-complete, under polynomial-time many-one reductions, if:
- It belongs to EXPTIME.
- Every problem in EXPTIME can be transformed into it by a polynomial-time computable mapping that preserves yes- and no-answers.
A polynomial-time reduction transfers an instance of one problem into an instance of another. Completeness identifies problems that are at least as difficult as every other problem in EXPTIME under this comparison.
An EXPTIME-complete problem cannot have a polynomial-time algorithm: otherwise every EXPTIME problem would lie in P, contradicting the time hierarchy theorem. Such problems also satisfy NP-hardness, because NP is contained in EXPTIME. Whether an EXPTIME-complete problem can belong to NP is unresolved; this would imply .
Bounded machine acceptance
A canonical EXPTIME-complete problem takes as input:
- a description of a deterministic Turing machine ;
- an input string ;
- a unary integer ;
and asks whether accepts within steps.
Direct simulation establishes membership in EXPTIME. For hardness, any EXPTIME computation with time bound can be represented by choosing . Because is written in unary and is polynomial in , the resulting instance can be constructed in polynomial time.
This bounded problem differs fundamentally from the unrestricted halting problem. The finite time limit makes exhaustive simulation a decision procedure.
Logic and verification
Satisfiability for propositional dynamic logic is a standard EXPTIME-complete problem. This logic expresses properties of programs using operations such as sequential composition, nondeterministic choice, and iteration.
EXPTIME-complete problems also occur in formal verification, especially where compact descriptions represent large transition systems or where the semantics involve adversarial choices. Complexity depends on the exact task: satisfiability, model checking, and strategy synthesis for related formalisms can belong to different complexity classes.
Alternation and game interpretation
A fundamental characterization is
where APSPACE denotes the problems decidable in polynomial space by an alternating Turing machine.
Alternation extends nondeterminism with two types of branching:
- Existential states accept if at least one successor accepts.
- Universal states accept if every successor accepts.
This creates a game-like interpretation. Existential choices correspond to moves by a player attempting to establish acceptance; universal choices correspond to moves by an adversary.
A polynomial-space alternating machine has exponentially many possible configurations. Acceptance can be determined by solving the associated finite game over this configuration space. Conversely, deterministic exponential-time computations can be decided using polynomial-space alternation.
This equivalence explains why EXPTIME appears naturally in adversarial problems. A position may have a compact description even when determining whether a player has a winning strategy requires reasoning over exponentially many positions.
The distinction between a compactly represented game and an explicitly listed game tree is important. If the entire tree is supplied as input, evaluation by minimax can be polynomial in the tree’s size, even though generating that tree from a compact initial description may require exponential resources.
Closure properties
EXPTIME is closed under several basic operations:
- Complement: exchanging a decider’s accepting and rejecting outcomes preserves its time bound.
- Finite union and intersection: running finitely many EXPTIME deciders takes exponential time in a polynomial.
- Polynomial-time many-one reductions: if reduces to in polynomial time and belongs to EXPTIME, then belongs to EXPTIME.
The reduction property follows because a polynomial-time transformation produces an output of polynomial length. Applying a -time algorithm to an output of length takes at most time, still an EXPTIME bound.
Closure under complement also means that coEXPTIME, the class of complements of EXPTIME languages, equals EXPTIME.
Interpretation and limitations
EXPTIME is a worst-case, asymptotic classification. It does not directly measure performance on typical instances, small inputs, or restricted families.
Several distinctions are important:
- Membership is not a lower bound. Every polynomial-time problem also belongs to EXPTIME.
- Completeness does not specify an exact exponential requirement. EXPTIME-completeness rules out polynomial-time algorithms but does not establish that a particular bound, such as , is optimal.
- An exponential search procedure does not establish completeness. Enumerating all assignments places the Boolean satisfiability problem in exponential time, but this alone says nothing about EXPTIME-hardness.
- Space and time differ. An EXPTIME algorithm may use exponential space, but EXPTIME membership does not require that much space. The relationship between polynomial space and exponential time is captured by the unresolved PSPACE–EXPTIME equality.
- Fine-grained hypotheses address different questions. The Exponential Time Hypothesis concerns subexponential algorithms for satisfiability and does not follow simply from the separation of P and EXPTIME.