EXPTIME

For example, the class 2-EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound.

It is also known that if P = NP, then EXPTIME = NEXPTIME, the class of problems solvable in exponential time by a nondeterministic Turing machine.

One of the most fundamental EXPTIME-complete problems is a simpler version of this, which asks if a DTM halts on a given input in at most k steps.

It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more.

By contrast, generalized games that can last for a number of moves that is polynomial in the size of the board are often PSPACE-complete.

Succinct circuits are simple machines used to describe some graphs in exponentially less space.