EXPTIME is the class of problems with yes-or-no answers that can be solved by a deterministic Turing machine in time 
, where 
is the input length and 
is a polynomial (Sedgewick
and Wayne). The big-O notation gives a worst-case
bound over all inputs of length 
.
An EXPTIME-complete problem belongs to EXPTIME and can express every problem in EXPTIME through a transformation computable in polynomial time that preserves the yes-or-no answer. Such problems cannot be solved in polynomial time by a deterministic Turing machine (Sedgewick and Wayne).
