EXPTIME

In complexity theory is EXPTIME (sometimes just EXP) for the complexity class of decision problems ( DTM ) can be decided by bounded in time by a deterministic Turing machine. is an arbitrary polynomial in the input length. Expressed in DTIME notation applies:

EXPTIME - completeness

The language is EXPTIME -complete.

Relation to other complexity classes

The following relations are known:

Since P to the time hierarchy theorem is a proper subset of EXPTIME, must be real at least a subset of relations P NP PSPACE EXPTIME.