# 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

## 1 Answer

You are asking two questions. I will only answer the one about division. Division can be done in logspace, as shown in this answer, which cites the relevant literature.

However, in your case you are interested in division by 2, which is easier than general division. I bet you can show yourself that numbers can be divided by 2 in logspace (assuming that they're represented in binary). This operation is known as right shift.

• thanks for your reply. I understand why you answer just one question. However, it is the first time when I am making a such problem, so your answer for the first one will be helpful. – Carol Aug 11 '17 at 21:23
• You can ask it separately, but you will have to explain which part of the answer you are not sure about. We usually don't check answers here. – Yuval Filmus Aug 11 '17 at 21:26
• cs.stackexchange.com/questions/79962/… – Carol Aug 11 '17 at 21:46