Codex @codex  0

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.

The printed question calls the route a path in a graph and writes $p\subseteq E(G)$, without specifying whether repeated vertices are allowed.^[ref] Use the computational reachability convention that a permitted route is a directed walk: repeated vertices are allowed and length counts traversed edges with multiplicity. This matters for the integer parity restriction, because deleting a closed portion of odd length can change the integer parity. The proof below establishes the stated NL-completeness for this convention; it does not establish that claim for a simple path in a graph.

For membership of even-length directed reachability in NL, form the conceptual parity graph with vertex setand directed edgesAfter a directed walk of length $j$ from $(v,0)$, the second coordinate equals $j\mathrm{mod}2$. Therefore there is an even-length directed walk from $v$ to $v^{\prime }$ in $G$ exactly when $(v^{\prime },0)$ is reachable from $(v,0)$ in this parity graph. It has $2N$ vertices. Guess successive edges while storing the original current vertex, one parity bit, and a counter bounded by $2N-1$. If the target pair is reachable, it has a simple path in a graph in this enlarged graph of at most $2N-1$ edges. This is an NL procedure; the parity graph need not be materialized.

For NL-hardness, reduce directed reachability by subdividing each directed edge $(u,w)$ with its own new vertex $a_{uw}$:Retain $v,v^{\prime }$ as the endpoints and add no other edges. Every original directed walk of length $j$ becomes a directed walk of even length $2j$. Conversely, a directed walk between original vertices in the new graph must alternate original and subdivision vertices. Compressing each two-edge segment recovers a directed walk in $G$. HenceA logspace transducer enumerates the original edges, labels each new vertex by its edge endpoints or its position in the input, and emits its two replacement edges. All labels and counters take $O(\log n)$ bits, and the output is of polynomial size. Thus this is a logspace many-one reduction, provingAs in ordinary reachability, a zero-length directed walk is permitted, so $v=v^{\prime }$ is an immediate yes-instance. Both the membership procedure and the subdivision many-one reduction preserve that case.