Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/computational-complexity/2/c/solution

Let , accepted by a fixed Nondeterministic Turing machine in at most steps on every computation branch, for a polynomial . Since the transition relation is finite, there is a fixed constant bounding the number of choices at any step. Every branch can be specified by a word over an alphabet of length over a -symbol choice alphabet, padding unused choices after halting.
A deterministic Turing machine enumerates all such choice sequences and simulates the corresponding branches for at most steps each. It accepts if some simulation accepts, and rejects after all have failed. Every possible accepting branch is included, and the time cutoff guarantees termination even on invalid choice sequences. A standard direct simulation has only polynomial overhead per branch, giving
for a suitable polynomial . This is a deterministic exponential time bound. Therefore
Here EXPTIME means the union of deterministic time bounds over fixed positive integers , allowing the usual constant factors and finitely many small inputs.

New to topics? Read the docs here!