<p>The answer is no unless L=P (and obviously yes if L=P).  To see this, fix a deterministic Turing machine (DTM) <i>M</i> which solves a P-complete problem in polynomial time, and consider a function <i>f</i> which maps a configuration of <i>M</i> to the configuration in the next time step.  Function <i>f</i> is just the simulation of one step in the DTM and can be computed in logarithmic space.  If you iterate this function <i>t</i> times, you can compute the configuration after <i>t</i> steps, and therefore you can decide whether DTM <i>M</i> accepts on a given input string within <i>t</i> steps.  If you can do this in logarithmic space, you have solved the P-complete problem in logarithmic space, and therefore L=P.</p>

CC BY-SA 3.0
2011-09-08T00:36:55.120Z
It may (or may not) be helpful to state the proof idea at a higher level, so here is an attempt: because a polynomial-time Turing machine does nothing but repeating a simple step polynomially many times, any additional power of P over that simple step must come from the very ability to repeat something polynomially many times.  (First I thought that this “high-level idea” was much easier to understand than what I had written as the answer, but after actually writing this comment, I am not so sure….)
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-08T02:00:48.857Z
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}$  )
Kaveh
CC BY-SA 3.0
2011-09-08T03:03:51.700Z
@Kaveh: In this question, the number of iterations is the input size, not logarithmic in the input size, and so I cannot understand your comment.  (I may well be missing something, because I am not familiar with descriptive complexity theory.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-08T03:30:15.770Z
right (I had an extra log). So it is $\mathsf{FO}[n]$.
Kaveh
CC BY-SA 3.0
2011-09-07T22:05:39.680Z
2011-09-07T22:05:39.680Z
Tsuyoshi Ito
<p>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? </p>

CC BY-SA 3.0
2011-09-07T18:00:14.600Z
Is this a homework problem?
Tyson Williams
CC BY-SA 3.0
2011-09-07T18:04:25.797Z
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
CC BY-SA 3.0
2011-09-07T20:30:58.343Z
Sorry for doubting the seriousness of your question and providing a wrong answer.
Tyson Williams
CC BY-SA 3.0
2011-09-07T22:36:52.353Z
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.
Aaron Sterling
<cc.complexity-theory><complexity-classes><reductions>
FL with polynomial number of log-space "reductions" still in FL?
Tom
# FL with polynomial number of log-space "reductions" still in FL?

(Asked by: username_0 on 2011-09-07)

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?

**Tags:** cc.complexity-theory, complexity-classes, reductions
> **Comments:**
> **username_1**: Is this a homework problem?  
> **username_0**: 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.  
> **username_1**: Sorry for doubting the seriousness of your question and providing a wrong answer.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-09-07. Score: 7 | Accepted answer

The answer is no unless L=P (and obviously yes if L=P). To see this, fix a deterministic Turing machine (DTM) *M* which solves a P-complete problem in polynomial time, and consider a function *f* which maps a configuration of *M* to the configuration in the next time step. Function *f* is just the simulation of one step in the DTM and can be computed in logarithmic space. If you iterate this function *t* times, you can compute the configuration after *t* steps, and therefore you can decide whether DTM *M* accepts on a given input string within *t* steps. If you can do this in logarithmic space, you have solved the P-complete problem in logarithmic space, and therefore L=P.

> **Comments:**
> **username_3**: It may (or may not) be helpful to state the proof idea at a higher level, so here is an attempt: because a polynomial-time Turing machine does nothing but repeating a simple step polynomially many times, any additional power of P over that simple step must come from the very ability to repeat something polynomially many times.  (First I thought that this “high-level idea” was much easier to understand than what I had written as the answer, but after actually writing this comment, I am not so sure….)  
> **username_4**: 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}$  )  
> **username_3**: @Kaveh: In this question, the number of iterations is the input size, not logarithmic in the input size, and so I cannot understand your comment.  (I may well be missing something, because I am not familiar with descriptive complexity theory.)  
> **username_4**: right (I had an extra log). So it is $\mathsf{FO}[n]$.  

---

