# FL with polynomial number of log-space "reductions" still in FL?

Suppose that $f: X \rightarrow X$ is computable in log-space. Given an input $x \in X$ where $x$ is encoded within $n$ bits, is $f^n(x)$ computable in log-space?

• Is this a homework problem? Sep 7 '11 at 18:00
• No, this is a serious question. I've developed an algorithm computable in log-space and I need this property to be true to compute f^n, but I don't know how it is called in the literature.
– Tom
Sep 7 '11 at 18:04
• Sorry for doubting the seriousness of your question and providing a wrong answer. Sep 7 '11 at 20:30
• Tom, it may be that your particular function has the property you need. Tsuyoshi's answer applies to an arbitrary logspace function. If your own function "feels weaker than full logspace," you might want to ask another question with more specifics about your algorithm. Sep 7 '11 at 22:36

• Essentially this is similar to $\mathsf{FO}[n^{O(1)}] = \mathsf{P}$ argument. But since the iteration is just $|x|$ (not an arbitrary polynomial in the input size, but only logarithmic in the input size), don't we get only $\mathsf{FO}[\lg n]$ which is just $\mathsf{AC^1}$? (but again, we don't know if $\mathsf{L}=\mathsf{AC^1}$ or $\mathsf{L}\subset\mathsf{AC^1}$ ) Sep 8 '11 at 2:00
• right (I had an extra log). So it is $\mathsf{FO}[n]$. Sep 8 '11 at 3:30