= Solution
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,\ldots,L-1$, compute
$$
t_i=x_i+y_i+c_i,\qquad
s_i=t_i\bmod2,\qquad
c_{i+1}=\left\lfloor\frac{t_i}2\right\rfloor.
$$
Reject 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> is
$$
\sum_{j<i}x_j2^j+\sum_{j<i}y_j2^j
=\sum_{j<i}s_j2^j+c_i2^i.
$$
It 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. Thus
$$
\boxed{\mathrm{Add}\in\mathrm L.}
$$
For 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 is
$$
\ell=\begin{cases}m+1,&c_m=1,\\m,&c_m=0.\end{cases}
$$
Indeed, 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\leq 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\operatorname{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>. Therefore
$$
\boxed{\mathrm{Pal\text{-}Add}\in\mathrm L.}
$$
Equivalently, 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.
Back to article page
