# Logarithmic reduction to another LOGSPACE problem

For words of the same length $u = u_1..u_n, v = v_1..v_n$ over an alphabet $A$ let $$u \circ v = u_1v_1...u_nv_n$$

Prove that if $L$ over $A \times A$ in in LOGSPACE then $$L' = \{uv : u \circ v \in L\}$$ is also in LOGSPACE

My solution: We try to log-reduce $L'$ to $L$. So, I mean when a machine $M_L$ tries to read an input then reducing function $f$ gives another input.

Let $I$ be an input tape, word $w = uv = u_1..u_nv_1..v_n, |w| = 2n$ and $w$ starts at 0th cell.

Now, we define $f$: $$f(i) = \left\{\begin{array}{lr} I[i/2] & \text{for } i \ even \\ I[i/2+n] & \text{for } i \ odd \end{array}\right]$$

My doubts:

1. Is it ok?
2. I used in $f$ division. Is is possible in $LOGSPACE$?
• Please ask only one question per question. – D.W. Aug 12 '17 at 2:14