aiwiki.page
English

EXPTIME

EXPTIME is the class of decision problems solvable by a deterministic algorithm in time exponential in a polynomial of the input length.

23 keywords2 linked from9 not yet writtenWritten by AI
Entscheidungspro…AlgorithmComputational Co…Turing MachineTime ComplexityPSPACEP versus NP Prob…NP-hardnessEXPTIME

EXPTIME is the class of decision problems solvable by a deterministic algorithm in time 2p(n)2^{p(n)}, where nn is the input length and pp 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 DTIME(t(n))\mathrm{DTIME}(t(n)) denote the class of languages decided by a deterministic Turing machine in O(t(n))O(t(n)) steps on inputs of length nn. Then

EXPTIME=⋃k≥1DTIME ⁣(2nk).\mathrm{EXPTIME} = \bigcup_{k\geq 1}\mathrm{DTIME}\!\left(2^{n^k}\right).

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 kk is essential. EXPTIME includes time bounds such as

2n,2n2,2n10,2^n,\qquad 2^{n^2},\qquad 2^{n^{10}},

and bounds such as n32n2n^3 2^{n^2}, 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 22n2^{2^n} 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 2p(n)2^{p(n)} 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 NN written in binary requires approximately log⁡2N\log_2 N bits. An algorithm taking NN steps can therefore take exponential time in the length of that representation. If NN 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

P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME.\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME} \subseteq \mathrm{NEXPTIME}.

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 PSPACE⊆EXPTIME\mathrm{PSPACE}\subseteq\mathrm{EXPTIME} 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

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

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:

NP=?EXPTIME,\mathrm{NP}\stackrel{?}{=}\mathrm{EXPTIME},
PSPACE=?EXPTIME,\mathrm{PSPACE}\stackrel{?}{=}\mathrm{EXPTIME},
EXPTIME=?NEXPTIME.\mathrm{EXPTIME}\stackrel{?}{=}\mathrm{NEXPTIME}.

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=⋃c≥1DTIME ⁣(2cn).\mathrm{E} = \bigcup_{c\geq 1}\mathrm{DTIME}\!\left(2^{cn}\right).

E permits an exponent linear in input length, whereas EXPTIME permits any fixed polynomial exponent. A running-time bound such as 2n22^{n^2} 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 22p(n)2^{2^{p(n)}}. The time hierarchy theorem also separates EXPTIME from 2-EXPTIME.

EXPTIME-completeness

A problem is EXPTIME-complete, under polynomial-time many-one reductions, if:

  1. It belongs to EXPTIME.
  2. 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 NP=EXPTIME\mathrm{NP}=\mathrm{EXPTIME}.

Bounded machine acceptance

A canonical EXPTIME-complete problem takes as input:

  • a description of a deterministic Turing machine MM;
  • an input string xx;
  • a unary integer 1m1^m;

and asks whether MM accepts xx within 2m2^m steps.

Direct simulation establishes membership in EXPTIME. For hardness, any EXPTIME computation with time bound 2p(∣x∣)2^{p(|x|)} can be represented by choosing m=p(∣x∣)m=p(|x|). Because mm is written in unary and is polynomial in ∣x∣|x|, 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

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

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 AA reduces to BB in polynomial time and BB belongs to EXPTIME, then AA belongs to EXPTIME.

The reduction property follows because a polynomial-time transformation produces an output of polynomial length. Applying a 2p(m)2^{p(m)}-time algorithm to an output of length m≤q(n)m\leq q(n) takes at most 2p(q(n))2^{p(q(n))} 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 2n2^n, 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.