4
$\begingroup$

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) $.

$\endgroup$
3
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – Shadower2222 Apr 27 '13 at 5:16

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.