Definition
EXPTIME Complexity Class
The complexity class EXPTIME contains all decision problems that can be solved by a deterministic Turing machine in exponential time.
- Time usage: for some constant
In other words, the running time may grow exponentially in the input size, but it must still be bounded by a fixed exponential function.
Idea
- EXPTIME contains problems that are still decidable, but may require a very large number of steps.
- “Exponential time” means the runtime can be exponential in the input size, but not worse than a fixed exponential bound.
- A brute-force search over an exponentially large game tree is a typical reason for a problem to lie in EXPTIME.
- EXPTIME-complete problems are considered intractable unless a major complexity-class collapse occurs.
Examples
Generalised Go winning strategy
Given an board position, the problem asks whether Player 1 has a winning strategy in the generalised game of Go.
This problem is in EXPTIME because the number of possible game states grows exponentially, and there is no polynomial bound on the duration of the game.
Datalog query evaluation
Evaluating queries in Datalog with recursion can be done in exponential time in the size of the input.
Hence, the problem lies in EXPTIME.