# Proving language in Space Complexity

I'd like to know if I have the right intuition and my answer is headed the correct way.

I am given a function $f = \{0, 1\}^* \rightarrow \{0, 1\}^*$ that is computable in space $O(\log n)$ assume that for every $x \in \{0, 1\}^*$, $f$ is length preserving, $|f(x)| = |x|$.

Define $$L = \left\{ x\#y \mid \ x, y \in \{0, 1\}^*, |x| = |y|, \ \text{and} \ f(x) = f(y)\right\}$$

I am suppose to prove that $L \in {\sf DSPACE}(\log n)$.

Please correct me if my intuition is incorrect.

My solution would be to build a decider $M$ which is a Turing machine.

$M$ takes inputs $x$ and $y$, run the function $f$ on input $x$ and $y$ and if the lengths of the two strings are equal then accept, otherwise reject.

Now the Turing machine runs in $O(\log n)$ because the function $f$ is computable in $O(\log n) + O(\log n) = O(\log n)$ and comparing the length returned by the function is $O(1)$ Thus the language is decidable by a Turing machine that is run in $O(\log n)$ and only takes Space $O(\log n)$.

Here is a rough idea how to solve this. You compare $f(x)$ and $f(y)$ character by character. Your tape is devided into 4 pieces. The first one is for simulating $f(x)$ the second one for $f(y)$, then you have two parts, one that counts which character of $x$ you are currently computig, and another $O(\log n)$ area that helps you to navigate. Now the programm looks like this

1. Determine $|x|$ and $|y|$ (store it in binary!) and check if there are the same.
2. Compute the first character of $f(x)$ by simulating it on your machine. Store the output in a TM-state. Pause the Computation of $f(x)$.
3. Walk $|x|+1$ step to the right.
4. Simulate $f(y)$ until you get the first character, check if it coincides with the start of $f(x)$, if no reject, otherwise continue.
5. Walk $|x|$ steps left.
6. Repeat the steps 2.-5. until you check $f(x)=f(y)$ completely.

I'm afraid you've misread the question. It is the sizes of $x$ and $y$ that need to be equal, not that of $f(x)$ and $f(y)$. Of course, in this case, since $f$ is length preserving, $|x| = |y|$ is the same as $|f(x)| = |f(y)|$. But what then about the second part, $f(x) = f(y)$?

Another reason that your algorithm doesn't work is that it uses linear space. Computing the function $f$ takes logarithmic space, but the output takes linear space. So if you store $f(x)$ and $f(y)$ on the work tape, you are using space $\Theta(n)$ rather than $O(\log n)$.

• EDITED NEW SOLUTION: Thanks I see the problem that lies in my algorithm and this is how I would fix the first issue. $M$ takes inputs $x \ and \ y$, Run $f$ on $\ x \ and \ y$, Check to see if the number of steps taken by $f$ on both inputs is equal and check if the length determined by the function for both inputs is equal. $M$ Accepts if it satisfies both conditions, otherwise $M$ Rejects. But I'm not entirely sure how to avoid the issue you stated about how the space complexity would be $O(n)$ when I'm really looking for $O(log n)$ Apr 27 '13 at 5:16