Some authors restrict p(n) to be a linear function, but a more common definition is to allow p(n) to be any polynomial.
The complexity class EXPSPACEcomplete is also a set of decision problems. A decision problem is in EXPSPACEcomplete if it is in EXPSPACE, and every problem in EXPSPACE has a 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. EXPSPACEcomplete might be thought of as the hardest problems in EXPSPACE.
EXPSPACE is a strict superset of EXPTIME, PSPACE, NPcomplete, NP, and P.
An example of an EXPSPACEcomplete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression).
If the Kleene star is left out, then that problem becomes NEXPTIMEcomplete, which is like EXPTIMEcomplete, except it is defined in terms of nondeterministic Turing machines rather than deterministic.
Search Encyclopedia

Featured Article
