7
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Is this a homework problem? $\endgroup$ Sep 7 '11 at 18:00
  • $\begingroup$ 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. $\endgroup$
    – Tom
    Sep 7 '11 at 18:04
  • $\begingroup$ Sorry for doubting the seriousness of your question and providing a wrong answer. $\endgroup$ Sep 7 '11 at 20:30
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 7 '11 at 22:36
7
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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….) $\endgroup$ Sep 8 '11 at 0:36
  • $\begingroup$ 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}$ ) $\endgroup$
    – Kaveh
    Sep 8 '11 at 2:00
  • 1
    $\begingroup$ @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.) $\endgroup$ Sep 8 '11 at 3:03
  • $\begingroup$ right (I had an extra log). So it is $\mathsf{FO}[n]$. $\endgroup$
    – Kaveh
    Sep 8 '11 at 3:30

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.