 Computational Complexity examination paper of the University of Oxford (2015)

The University of Oxford computer science finals examination dated Wednesday 3 June 2015, Trinity Term 2015. The four-page original has three questions, on computability theory, time complexity and logarithmic space. The public examination-paper archive supplied by the University of Oxford contains it as 2015-complex.pdf. Questions 2 and 3 are marked corrected. Question 3(e) uses the word path in a graph without specifying whether repeated vertices are permitted; the even-length directed reachability proof uses directed walks with length counted with multiplicity.