How do we prove $M$ that is a deterministic random access machine that decides a problem $A$ for an input $i$, and $u_M(i)$ is the set of addresses of those registers that occur at least once with $s$ steps and a configuration of $C_0,\dots,C_s$ where each configuration is of the form $C_i=(k_i,R_i)$, were $k_i$ is the program counter and a mapping $R_i$ runs in polynomial time if it runs in logarithmic space.

  • 1
    $\begingroup$ Standard textbook exercise. What have you done so far? $\endgroup$
    – G. Bach
    Oct 20 '13 at 14:01
  • $\begingroup$ What I have done so far is that the maximal configuration for a problem that is is decidable in $log(x)$ space is $2^{o(used(x))}$ since each space can either be used or unused and this is the total number of configuration possible. Just want to know if I am on the right track and besides @G.Bach what is the point of posting a question you already know $\endgroup$
    – fudu
    Oct 21 '13 at 17:43
  • $\begingroup$ The point is that you showed no effort besides posting the question, and this website is not here to solve exercises for people. I couldn't know whether you had done anything, there are quite a lot of people who come here and expect solutions to problems they have not even tried to solve. That is one of the reasons why this network expects people to also post what they tried when they post a question. $\endgroup$
    – G. Bach
    Oct 21 '13 at 17:55

Hint: If the program runs in logarithmic space then there are only polynomially many possible configurations.


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.