EXPTIME

EXPTIME (sometimes written EXP) is a complexity class in computational complexity theory. It represents the set of all decision problems that can be solved by a deterministic Turing machine in exponential time. More formally, a problem is in EXPTIME if there exists a deterministic Turing machine that solves it in $O(2^{p(n)})$ time, where $p(n)$ is a polynomial function of the input size $n$. This is often denoted as DTIME($2^{poly(n)}$).

Formal Definition

A language $L$ is in EXPTIME if there exists a deterministic Turing machine $M$ and a polynomial $p(n)$ such that:

1. $M$ decides $L$.
2. The running time of $M$ is $O(2^{p(n)})$.

Relationship to Other Complexity Classes

EXPTIME is a significant class within the polynomial hierarchy and related complexity classes. Its position is well-defined relative to several other common classes:

• P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE

While the exact relationships between P, NP, and PSPACE are unknown (e.g., P vs. NP), some strict inclusions are known concerning EXPTIME:

• P $\subsetneq$ EXPTIME: It is known that P is strictly contained within EXPTIME, meaning there exist problems solvable in exponential time that cannot be solved in polynomial time. This separation is a fundamental result in complexity theory.
• NP $\subsetneq$ NEXPTIME: Similarly, NP is strictly contained within NEXPTIME (non-deterministic exponential time).
• PSPACE $\subsetneq$ EXPSPACE: PSPACE is also strictly contained within EXPSPACE (exponential space).

It is also known that PSPACE $\subseteq$ EXPTIME. However, whether PSPACE is strictly smaller than EXPTIME (i.e., PSPACE $\subsetneq$ EXPTIME) is an open question, although it is widely believed to be true.

EXPTIME-Complete Problems

A problem is said to be EXPTIME-complete if it is in EXPTIME and every problem in EXPTIME can be reduced to it in polynomial time. EXPTIME-complete problems are considered the "hardest" problems in the EXPTIME class. Many problems involving games played on an $n \times n$ board, where $n$ is part of the input, are EXPTIME-complete. Examples include:

• Generalized Chess (determining if the first player has a winning strategy from a given position on an $n \times n$ board).
• Generalized Go (with a finite number of moves).
• Generalized Checkers.
• Certain types of planning problems.

The significance of EXPTIME lies in defining the boundary of problems that are computationally feasible, albeit often practically intractable for large inputs, within a reasonable amount of exponential time. Problems outside EXPTIME, for example, those requiring doubly exponential time, are considered even more challenging.