EXPTIME

Some authors restrict p(n) to be a linear function, but a more common definition is to allow p(n) to be any polynomial. If p(n) is a linear function, the resulting class is often called E, and is obviously a subset of EXPTIME.

EXPTIME is known to be a subset of EXPSPACE and a superset of PSPACE, NP-complete, NP, and P. That is significant because it is currently unknown which (if any) of those four sets are equal to each other. It is known however that P is a strict subset of EXPTIME.

The complexity class EXPTIME-complete is also a set of decision problems. A decision problem is in EXPTIME-complete if it is in EXPTIME, and every problem in EXPTIME has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. EXPTIME-complete might be thought of as the hardest problems in EXPTIME.

Examples of EXPTIME-complete problems include the problem of looking at a Chess or Go position, and telling whether the first player can force a win. Actually, the games have to be generalized by playing them on an n × n board instead of the usual board with fixed size. That is because complexity classes like EXPTIME-complete are defined by asymptotic behavior as the problem size grows without bound. Most board games are easier to solve than Chess and Go. See PSPACE-complete for examples.

There exist oracles X for which EXPTIME^X = PSPACE^X = NP^X (See the oracle machine article for an explanation of the EXPTIME^X notation).

Referenced By