Some authors restrict p(n) to be a linear function, but a more common definition is to allow p(n) to be any polynomial.
EXPTIME is known to be a subset of EXPSPACE and a superset of PSPACE, NPcomplete, 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 EXPTIMEcomplete is also a set of decision problems. A decision problem is in EXPTIMEcomplete if it is in EXPTIME, and every problem in EXPTIME has a polynomialtime manyone reduction to it. In other words, there is a polynomialtime algorithm that transforms instances of one to instances of the other with the same answer. EXPTIMEcomplete might be thought of as the hardest problems in EXPTIME.
Examples of EXPTIMEcomplete 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 EXPTIMEcomplete are defined by asymptotic behavior as the problem size grows without bound. Most board games are easier to solve than Chess and Go. See PSPACEcomplete 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).
Search Encyclopedia

Featured Article
