Let $A$ be a language and define $$ CYCLE(A)= \{ yx | xy \in A \} $$ I need to prove, or disprove, $ A\in LSPACE \Longrightarrow CYCLE(A)\in LSPACE $.

First I tried to prove $CYCLE(A) \le_{L} A$ which if true means that if $A\in LSPACE$ then $CYCLE(A)\in L$, hence I tried to define a log space transducer $M$ that compute a log space reduction from $CYCLE(A)$ to $A$:

M="for input $\langle w \rangle$:

  1. for every symbol $s$ in $w$:
    1. $y = w[:s]$, $x = w(s:]$
    2. build $xy$ on the working tape
    3. run the Turing machine that decides $A$ on $xy$
    4. if it accepts $xy$ write $xy$ to output and accept"

But this isn't good, as while $A$ is known to be in $LSPACE$, and therefore its Turing machine runs in O($log{n}$) space, the building of $xy$ each time will take $O(n)$ space.

I then tried to build a Turing machine that decides $CYCLE(A)$ in O($log{n}$) but the idea seems to be exactly as the transducer: find a possible split to $yx$, build $xy$ and run $A$'s Turing machine on $xy$ and if it accepts, accept the input. But again building $xy$ will take O($n$) space.

At this point I shifted to try to disprove. I need to find language $A$ such that $A\in LSPACE$ but $CYCLE(A)\notin L$, but the more I think about it the more I lean towards the hypothesis being true, yet I'm unable to find how to prove it.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.