Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 3 / f

The binary numeral system representation is taken to be canonical, with no leading zeroes, for each positive integer. Delimiters separate the components of a pair or triple. Syntax, positivity and this representation convention can all be checked in logarithmic space. The useful principle is that a large integer need not be stored in order to compute its digits one at a time.

First consider Add. Let $x_i,y_i,z_i$ denote the binary digits in position $i$, counting from the least significant position $i=0$ and taking out-of-range digits to be zero. Count the component lengths, and let $L$ be their maximum. Start with arithmetic carry $c_0=0$. For $i=0,\dots ,L-1$, computeReject if $s_i\ne z_i$ at any position. After the last position, reject if $c_L=1$; otherwise accept. The final arithmetic carry check prevents accepting a result with an omitted high digit, such as the false equality $11_2+11_2=10_2$ obtained by retaining only two binary digits.

The binary-addition carry invariant isIt holds initially and is preserved by the displayed one-column equations. At the end, it proves that the comparisons and the final arithmetic carry check succeed exactly when $x+y=z$. Each requested binary digit is recovered by scanning the corresponding input field and counting to its position. The length counters, position $i$ and scan counters require $O(\log n)$ bits, while $c_i$ and $t_i\in \{0,1,2,3\}$ require constant space. ThusFor Pal-Add, construct a logspace transducer producing the canonical binary numeral system representation of $x+y$. Put $m=\max (|x|,|y|)$. One least-to-most-significant pass using the same recurrence determines the final arithmetic carry $c_m$. Positivity and canonical representations imply that the sum's digit length isIndeed, one summand is at least $2^{m-1}$ and both are less than $2^m$. For each output position, from $\ell -1$ down to $0$, recompute the required sum digit from scratch: reset the arithmetic carry to zero and run the column recurrence from position $0$ up to the requested position, reading input digits by scans. Positions beyond the summands use zero digits, so position $m$ correctly emits the possible final arithmetic carry. Emit only the requested digit, then reuse the work space for the next position.

This produces most-significant-first output with $\ell \le m+1$ digits. It uses $O(\log n)$ work space because it retains only a fixed number of digit indices, lengths, scan counters and one arithmetic carry; it never stores the whole sum. A direct implementation with repeated whole-input scans uses at most $O(n^3)$ time complexity, which is sufficient here. Hence $(x,y)\mapsto \mathrm{bin}(x+y)$ is a logspace-computable function.

Finally simulate the assumed L decider for binary palindrome on this virtual output, using logspace composition by recomputation from part (b). Whenever the simulated input head asks for a digit, rerun the addition logspace transducer until it emits that digit. The virtual input length is $O(n)$, so both its work space and the addition work space are $O(\log n)$. The simulation accepts exactly when the canonical representation of $x+y$ is a binary palindrome. ThereforeEquivalently, one could directly compare the sum digits in positions $i$ and $\ell -1-i$, recomputing each digit by the same recurrence. This gives the same logarithmic space conclusion without ever writing the full sum on a work tape.