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$?
  • $\begingroup$ Please ask only one question per question. $\endgroup$ – D.W. Aug 12 '17 at 2:14

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.

  • $\begingroup$ 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. $\endgroup$ – Carol Aug 11 '17 at 21:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 11 '17 at 21:26
  • $\begingroup$ cs.stackexchange.com/questions/79962/… $\endgroup$ – Carol Aug 11 '17 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.