Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity (A12071W1)

Solutions to all three questions of the University of Oxford computer science finals paper held on 3 June 2015, Trinity Term 2015. The printed cover gives paper code A12071W1. Questions 2 and 3 are marked corrected in the source.^[ref]

The solutions use the original printed notation; the integer parity convention needed in Question 3(e) is stated there explicitly.

Exactly the regular languages. A read-only-from-left Turing acceptor has only its current control state as usable memory: it never changes a tape symbol, and its head never returns to an earlier cell. This is the behaviour of a deterministic finite automaton while it reads the input.

To make the correspondence precise, retain the control states and the transitions on the input alphabet. Replace accepting and rejecting halts by absorbing states, so that halting before the end of a word over an alphabet has the same effect on every continuation. For each remaining state $q$, follow the transitions on blank symbols and mark $q$ accepting in the deterministic finite automaton exactly when this blank-only continuation eventually accepts. This marking is a finite calculation: either a halting state is reached or a state repeats, after which the blank-only run loops. The resulting deterministic finite automaton accepts exactly the same formal language as the read-only-from-left Turing acceptor. If the latter is a decider, the blank-only run from every reachable end-of-input state halts.

Conversely, simulate any deterministic finite automaton by a read-only-from-left Turing acceptor, using its state transitions while reading the input. At the first blank symbol, halt and accept or reject according to the current deterministic finite automaton state. This machine halts on every input and decides the required regular language.

Rice's theorem, in its formal language version, says: every nontrivial property of the computably enumerable language accepted by a Turing machine has an undecidable set of machine descriptions. Here nontrivial means that some computably enumerable language has the property and some does not. The property must be an extensional property of programs: any two Turing machines accepting the same formal language must agree about it. It need not be a property of all formal languages, including those no Turing machine accepts.

Let $\mathcal{P}$ be such a property and writeWe prove the theorem by a many-one reduction from the halting problem. First suppose the empty language is not in $\mathcal{P}$. Nontriviality provides a fixed Turing machine $B$ with $\mathcal{L}(B)\in \mathcal{P}$. Given a Turing machine $M$ and a word over an alphabet $w$, effectively construct a Turing machine $N_{M,w}$ which, on input $x$, first simulates $M$ on $w$. If that simulation ever halts, it simulates $B$ on $x$ and accepts precisely when $B$ accepts. If the first simulation never halts, it never accepts $x$.

The Turing machine encoding of $N_{M,w}$ is computable from those of $M,w$: the description merely embeds $M,w$ and the fixed simulator for $B$. Constructing it does not require predicting whether $M$ halts. Its accepted formal language isConsequentlyA decider for $I_{\mathcal{P}}$ would therefore decide the halting problem, a contradiction. Invalid descriptions can be mapped to a fixed description of a machine accepting the empty language, if the many-one reduction is formulated on all strings.

If the empty language does belong to $\mathcal{P}$, apply the preceding argument to the opposite property, within the computably enumerable languages. This opposite property is still nontrivial and excludes the empty language. A hypothetical decider for $I_{\mathcal{P}}$ would decide the opposite property's index set by first rejecting malformed Turing machine encodings and otherwise reversing its answer. The opposite property is undecidable by the first case, giving the required contradiction in this case too.

For example, takeThis is a decidable language: check that the input is a valid Turing machine encoding, count its declared states, and test the count's integer parity. There are Turing machines with even state counts and Turing machines with odd state counts, so the formal language contains some but not all valid descriptions.

There is no contradiction with Rice's theorem because this is a syntactic property of the description. Add one unreachable state to a Turing machine, assigning any permitted transitions to it. The accepted formal language is unchanged, while the integer parity of the state count changes. Thus the property is not an extensional property of programs, which is an essential hypothesis of Rice's theorem.

${\mathcal{L}}_{\ell 3}$ is undecidable. The condition depends only on the accepted formal language. It holds for a Turing machine accepting the empty language, and fails for a Turing machine accepting the singleton $\{aaaa\}$, where $a$ is an alphabet symbol. It is therefore a nontrivial extensional property of programs, and Rice's theorem applies. In particular, the condition does not assert that the machine halts on every input; nonacceptance of long words over an alphabet may result from rejection or from an infinite computation.

${\mathcal{L}}_{1\mathrm{T}}$ is a decidable language: it consists of every valid Turing machine encoding. Every multitape Turing machine has an equivalent single-tape Turing machine. To see this, represent the finitely used portions of its tapes on one tape, separated by delimiters, and mark each simulated head position. To simulate one step, scan these portions to read the marked symbols, retain this fixed number of symbols and the control state in finite control, and scan again to update the symbols and head marks. Extend a represented portion with a blank cell when necessary. Each simulated step takes finitely many real steps.

The single-tape Turing machine accepts exactly when the simulated multitape Turing machine accepts; infinite computations remain infinite. The simulation may increase time complexity, but the question only asks about accepted formal languages. Hence a decider simply checks the syntax of the Turing machine encoding and accepts every valid description. Rice's theorem does not make this property undecidable, because the property is true of every computably enumerable language and is therefore trivial in the theorem's sense.

The clique decision problem is a decidable language: on a valid finite graph and an integer $k$, reject if $k$ exceeds the number of vertices, and otherwise examine all $k$-element subsets of vertices, accepting if one is a clique. Each candidate can be checked by examining all its pairs of distinct vertices. This finite search gives at least one Turing machine deciding the problem, without any claim of polynomial time.

By well-ordering of the natural numbers, there is a least state count $n_0$ among Turing machines deciding the clique decision problem. For every $n\ge n_0$, add $n-n_0$ unreachable states to a machine with $n_0$ states. Its behaviour on every input is unchanged, and it has exactly $n$ states. For $n<n_0$ there is no such machine, by minimality. ThusA Turing machine with the fixed constant $n_0$ in its description decides this threshold language by validating the input and comparing its value with $n_0$. The argument proves the existence of a decider; it does not compute the smallest possible clique decision problem decider. There is no need to search through machine descriptions and attempt to certify their behaviour on every input.

Let $V$ be the decidable language of syntactically valid descriptions $\mathrm{enc}(M)\#\#w$. ThenHere the complement of a set on the left is taken in all words over an alphabet, while the non-halting problem only has valid machine-and-input descriptions as instances. Any malformed description belongs to $\overline{{\mathcal{L}}_{\mathrm{H}}}$ but not to ${\mathcal{L}}_{\mathrm{NH}}$. For example, the empty word has no separating ##, so cannot be a valid instance under the displayed encoding.

Fix valid descriptions $h$ and $\ell$ of, respectively, an immediately halting Turing machine on the empty word and a Turing machine looping forever on the empty word. ThenFor the first many-one reduction, use the total computable functionFor a valid input, nonmembership in ${\mathcal{L}}_{\mathrm{H}}$ is exactly membership in ${\mathcal{L}}_{\mathrm{NH}}$, so retaining it is correct. Every invalid input is a yes-instance of $\overline{{\mathcal{L}}_{\mathrm{H}}}$, and $f$ sends it to the fixed yes-instance $\ell$. Therefore $x\in \overline{{\mathcal{L}}_{\mathrm{H}}}$ if and only if $f(x)\in {\mathcal{L}}_{\mathrm{NH}}$.

For the reverse many-one reduction, useThe equivalence again holds on valid inputs. Invalid inputs are no-instances of ${\mathcal{L}}_{\mathrm{NH}}$, and $h$ is a no-instance of $\overline{{\mathcal{L}}_{\mathrm{H}}}$. Syntax checking terminates, so $g$ is also a total computable function. We have proved

Writing $\mathrm{PTime}$ as P and $\mathrm{co}\text{-}\mathrm{PTime}$ as co-P, the known relationships among the four complexity classes areThe equality supplies both inclusions between P and co-P, and it also gives co-P $\subseteq$ NP and co-P $\subseteq$ co-NP.

For the equality, a deterministic polynomial-time algorithm halts on every input; interchange its accepting and rejecting outcomes to decide the complement of a set in the same polynomial time. For P $\subseteq$ NP, a Nondeterministic Turing machine can simply make no choices and follow the deterministic computation. Finally, if $A\in \mathrm{P}$, then $\overline{A}\in \mathrm{P}\subseteq \mathrm{NP}$, whence $A\in \mathrm{co}\text{-}\mathrm{NP}$ by the definition of co-NP.

Neither NP $\subseteq$ co-NP nor co-NP $\subseteq$ NP is known; either would imply equality by taking complements. Nor is either inclusion of P into NP or co-NP known to be strict. These unresolved relationships must not be presented as strict separations.

The linear speedup theorem concerns multitape Turing machines whose finite control and tape alphabet may change. Formally, for $k>1$, if a deterministic $k$-tape Turing machine decides $A$ within $T(n)$ steps on every input of length $n$, then for every constant $c>0$ there is a deterministic $k$-tape Turing machine deciding the same formal language withThe additive constant is independent of $n$; in the usual normalized formulation the bound is $T(n)/c+n+2$, with the integer-rounding convention absorbed in the constant.^[ref]

The construction packs a fixed number of old tape symbols into each new symbol and uses a larger finite control to simulate blocks of old steps. Initial input packing explains the additive linear term. If $T(n)/n\to \infty$, choosing a larger constant $c$ makes the total asymptotic time complexity an arbitrarily small constant multiple of $T(n)$.

It does not promise arbitrary speed increases on fixed hardware. Larger packed symbols and transition tables cease to be single constant-cost hardware operations without limit. The theorem also retains the input-reading overhead. It is a statement about changing the abstract machine description and primitive operations, rather than an unlimited implementation optimization on one processor.

Let $A\in \mathrm{NP}$, accepted by a fixed Nondeterministic Turing machine $M$ in at most $p(n)$ steps on every computation branch, for a polynomial $p$. Since the transition relation is finite, there is a fixed constant $b\ge 2$ bounding the number of choices at any step. Every branch can be specified by a word over an alphabet of length $p(n)$ over a $b$-symbol choice alphabet, padding unused choices after halting.

A deterministic Turing machine enumerates all $b^{p(n)}$ such choice sequences and simulates the corresponding branches for at most $p(n)$ 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 $q$. This is a deterministic exponential time bound. ThereforeHere EXPTIME means the union of deterministic time bounds $2^{n^d}$ over fixed positive integers $d$, allowing the usual constant factors and finitely many small inputs.

Entail is co-NP-complete under polynomial-time many-one reductions. For valid propositional formulas, semantic entailment holds exactly when the logical conjunction of the premise and the conclusion's logical negation is an unsatisfiable Boolean formula:A counterexample to semantic entailment is a Boolean valuation making $\phi$ true and $\psi$ false. Guessing one bit for each distinct Boolean variable and evaluating both propositional formulas is a polynomial-time algorithm. Thus the complement of Entail belongs to NP. Malformed descriptions, also in that complement, can be accepted after a deterministic syntax check. Hence Entail belongs to co-NP as a formal language over all strings.

For hardness, the unsatisfiable Boolean formula problem is co-NP-hard: if $A\in \mathrm{co}\text{-}\mathrm{NP}$, then $\overline{A}\in \mathrm{NP}$, and the permitted NP-hardness of SAT supplies a polynomial-time many-one reduction $r$ withWe may ensure $r(x)$ is always a valid propositional formula, replacing any malformed output by a fixed contradiction. It follows that $x\in A$ exactly when $r(x)$ is unsatisfiable. This justifies using the unsatisfiability problem as a hardness source without an extra assumption.

Map a valid propositional formula $\theta$ towhere $p$ is a fixed Boolean variable. The second propositional formula is false under every Boolean valuation. Consequently it is entailed by $\theta$ precisely when no Boolean valuation satisfies $\theta$. ThusThe output has only constant additional length and is computable in polynomial time. If the source unsatisfiability language rejects malformed strings, map them to the fixed no-instance $⟨p,p\wedge \neg p⟩$. This completes a total polynomial-time many-one reduction and proves the claimed co-NP-completeness.

The clique decision problem belongs to NP. First reject $k>|V(G)|$. Otherwise a complexity certificate lists $k$ distinct vertices. Check distinctness and test that each of the $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ pairs is an edge. Under a conventional explicit graph encoding, the complexity certificate length and verification time complexity are polynomial in the input length. The early rejection is relevant when $k$ is given in the binary numeral system.

For NP-hardness, first transform a SAT instance into an equisatisfiable conjunctive normal form $F=C_1\wedge \cdots \wedge C_m$ of polynomial size using a Tseitin transformation. This step avoids the possibly exponential increase caused by distributing arbitrary Boolean formulas into conjunctive normal form. Introduce a fresh Boolean variable for each subformula, constrain it to have the connective's truth value using a constant number of Boolean clauses, and require the top variable to be true. A Boolean valuation of the original Boolean variables satisfies the original Boolean formula exactly when it extends to a satisfying assignment of these constraints.

Create one vertex for each occurrence of a Boolean literal in each Boolean clause. Join two such vertices by an edge exactly when they belong to different Boolean clauses and their Boolean literals are not a variable and its logical negation. Set $k=m$. There are at most as many vertices as Boolean literal occurrences and at most quadratically many edges, so this construction takes polynomial time.

If $F$ has a satisfying assignment, choose one true Boolean literal occurrence from each Boolean clause. No two selected Boolean literals are contradictory, so their $m$ vertices form a clique. Conversely, an $m$-clique contains at most one vertex from each Boolean clause, because there are no edges within a Boolean clause. It therefore selects exactly one occurrence from each of the $m$ Boolean clauses. The selected Boolean literals are pairwise noncontradictory, so assign their Boolean variables the indicated truth values and assign any other Boolean variables arbitrarily. This Boolean valuation satisfies every Boolean clause.

An empty Boolean clause gives no vertex in its group, correctly preventing an $m$-clique. An empty logical conjunction can instead be mapped to a fixed yes-instance, avoiding any convention about $k=0$. Malformed SAT descriptions can be mapped to a fixed no-instance. We have proved

To establish strong NP-completeness, use an explicit adjacency matrix encoding for a finite simple graph, with enough length information to recover its number $N$ of vertices. Let $\mathrm{bin}(k)$ be the canonical binary numeral system representation of the nonnegative integer $k$. Defineand, using the unary numeral system for $k$,The surrounding pairing syntax delimits the two components, so the empty unary field can encode $k=0$ if zero is included in the convention for natural numbers. Malformed descriptions are excluded from both formal languages.

Fix a unary no-instance $u_0$, for example one isolated vertex with requested size $2$. The polynomial-time many-one reduction isMap malformed inputs to $u_0$ too. When $k\le N$, only the numerical representation changes, so the existence of a $k$-clique is unchanged. When $k>N$, the original instance is false, since a subset of vertices cannot be larger than the whole vertex set; $u_0$ is false as required.

The important size bound is $k\le N$ in the branch that writes $1^k$. The original explicit graph description already has length at least $N$, so the output has polynomial length and can be written in polynomial time. If a huge binary numeral system value $k$ is supplied, compare it with $N$ using its digit length and, when needed, a digit comparison; do not first allocate or print $k$ symbols. Merely replacing an unrestricted binary $k$ by $1^k$ would not be a valid polynomial-time reduction.

Thus ${\mathcal{L}}_{\mathrm{Clique}}{\le }_p{\mathcal{L}}_{u\mathrm{Clique}}$. The unary version is in NP by the same clique complexity certificate verification, and is NP-hard by this polynomial-time many-one reduction and part (e). ThereforeThis conclusion uses the conventional explicit graph encoding; a succinct circuit description of a graph would be a different input representation and a different problem.

Use Turing machines with a two-way read-only input tape, bounded by endmarkers, and a fixed finite number of read-write work tapes over a fixed finite alphabet. Work-tape cells count towards space complexity; the read-only input does not. For input length $n$, use $O(\log (n+2))$ to include the small-length cases.

$\mathrm{Logspace}$, or L, is the class of formal languages decided by a deterministic such machine using at most $c\log (n+2)$ work-tape cells for some fixed constant $c$. It must halt on every input and accept exactly the members.

$\mathrm{NLogspace}$, or NL, is the class of formal languages accepted by a Nondeterministic Turing machine with the same work-space bound on every computation branch. An input is accepted if and only if at least one branch accepts. One may require all branches to halt: the configuration graph has only a polynomial number of vertices, so a logarithmic space counter can stop any branch that has taken more steps than that bound. If an accepting computation exists, one exists with no repeated Turing machine configuration, so this convention does not change the complexity class.

In standard space complexity notation,

A logspace transducer is a deterministic Turing machine with a read-only input tape, $O(\log (n+2))$ read-write work space, and a write-only output tape. It emits symbols successively and cannot reread the output; that output is not charged as working memory. For a total function it must halt on every input. A logspace-computable function $f$ is a total function whose output $f(x)$ is produced by such a logspace transducer on input $x$.

A logspace many-one reduction $A{\le }_m^{\log }B$ is a logspace-computable function $f$ such thatfor every string $x$. The logarithmic space bound permits a polynomial-length output, even when that output does not fit in work space. Indeed, a halting logspace transducer cannot repeat its state, input-head position and work-tape contents and head positions: the unreadable output cannot affect its subsequent behaviour. There are only a polynomial number of such internal Turing machine configurations, hence a polynomial bound on the number of steps and output symbols.

To prove a formal language $B$ is NL-complete, first give an NL acceptance procedure for $B$. Then show every $A\in \mathrm{NL}$ has a logspace many-one reduction to $B$. Alternatively, reduce one already NL-complete formal language to $B$, using transitivity of logspace many-one reductions.

Transitivity requires logspace composition by recomputation, rather than storing the intermediate output. To compose $g$ with $f$, simulate the logspace transducer for $g$ with a virtual input $f(x)$. Retain its virtual input-head position in $O(\log n)$ bits. Whenever it asks for a symbol, rerun the logspace transducer for $f$ from the beginning and count its output symbols until that position is reached. Since $|f(x)|$ is polynomial in $n$, the simulated work space $O(\log |f(x)|)$ and all output-position counters are $O(\log n)$. Repeated runs reuse their storage. This proves closure under composition and explains why the hardness argument works.

Let a deterministic Turing machine $M$ decide $A$ with at most $s(n)=c\log (n+2)$ work-tape cells. Fix an input $x$ of length $n$. A Turing machine configuration is determined by the control state, the read-only input-head position, the work-tape contents, and the work-head positions. For one work tape with alphabet $\Gamma$, their number is bounded, up to harmless fixed factors, byThe factors respectively count the state, input-head position, work-head position and work-tape contents. With a fixed number $r$ of work tapes, replace the last two factors by $(s(n)+1{)}^r|\Gamma {|}^{rs(n)}$ if each tape is allowed $s(n)$ cells; this still gives a valid polynomial upper bound. Two-way work tapes only change fixed factors in the head-position bounds.

Sincethere are at most $(n+2{)}^d$ Turing machine configurations for some constant $d$ depending on $M$. If a deterministic computation repeats one of its Turing machine configurations on the fixed input, all subsequent steps repeat too, so it never halts. But $M$ is a decider. It therefore halts before any repetition and takes at most a polynomial number of steps. The same Turing machine is consequently a polynomial-time algorithm, establishingIt would be incorrect to count just the work-tape contents and omit the read-only input-head position; that position is part of the Turing machine configuration even though the input itself is not charged as work space.

Directed reachability is NL-complete under logspace many-one reductions. For membership, let $N$ be the number of vertices. Store a current vertex, initially $v$, and a counter initially zero. Accept immediately if the current vertex is $v^{\prime }$. Otherwise guess a next vertex, verify by scanning the input that the appropriate directed edge exists, move there and increment the counter. Reject a branch that has made $N-1$ steps without reaching $v^{\prime }$.

Whenever a directed walk reaches $v^{\prime }$, removing closed portions between repeated vertices produces a path in a graph with at most $N-1$ edges. Thus this bound preserves all yes-instances. The current and guessed vertices and the counter use $O(\log N)$ bits, while adjacency checks only need repeated read-only input scans. All branches halt, so directed reachability belongs to NL.

For hardness, let $A\in \mathrm{NL}$ and fix a Nondeterministic Turing machine $M$ accepting $A$ in $O(\log n)$ work space. On input $x$, construct its configuration graph $C_x$. A vertex is a possible Turing machine configuration within the fixed work-space bound. Put a directed edge $C\to D$ exactly when one legal transition of $M$ on $x$ changes $C$ into $D$. Take the initial Turing machine configuration as source, and add a fresh target $t$ with an incoming edge from every accepting Turing machine configuration. ThenThere are only a polynomial number of Turing machine configurations, by the count used in part (c). More importantly, their encodings have length $O(\log n)$. A logspace transducer can enumerate candidate encodings and pairs of candidate encodings with $O(\log n)$ bits of counters. For each pair, it checks the finite transition rule, the scanned input symbol and the local work-tape change using $O(\log n)$ work space. It emits the corresponding adjacency matrix entry or edge-list record. Invalid candidate encodings may be discarded or represented by isolated vertices.

The configuration graph is thus output by a logspace transducer, rather than stored in its work tapes. This supplies the required logspace many-one reduction from every $A\in \mathrm{NL}$ and proves NL-completeness.

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.

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.