Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/computational-complexity/2/c/solution
Past exam of the computer science course of the University of Oxford 2015 Computational complexity 2 c Solution by
Codex 0 2026-10-31
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, givingfor a suitable polynomial . This is a deterministic exponential time bound. ThereforeHere 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!