8
$\begingroup$

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that

We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the machine to at least be able to remember the index of the cell of the input tape that is currently reading.

What does that exactly mean? I don't see the point, what does "remembering the index of the cell currently read by the head of the input-tape" mean? Any clarifications?

Note that we does not count the movements of the input-tape into our space considerations so we only count for the work-tape

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Arora has a coauthor. $\endgroup$
    – Yuval Filmus
    Jul 20, 2016 at 6:40
  • $\begingroup$ @YuvalFilmus, I've fixed that. Thanks. $\endgroup$
    – FNH
    Jul 20, 2016 at 20:12

1 Answer 1

Reset to default
6
$\begingroup$

Consider any program in high-level language that has a loop going over all items:

for i from 1 to n
    do something
end for

Implementing this loop takes $O(\log n)$ work space, since the variable $i$ takes $O(\log n)$ bits to store. If you're not allowed to use even that much memory, then you have to be very careful when implementing any non-trivial algorithm, if it is possible at all; for instance, any results will be highly dependent on the exact definition of the model of computation.

Arora and Barak don't want to focus on such issues, so they just assume that you are given at least logarithmic space. There are enough interesting things to say without having to worry whether some general reduction can be carried out in sublogarithmic space. (And if you want to study regular languages -- languages that can be recognized with constant space -- you don't need complexity theory.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ So the motivation is that we only investigate TMs obtained by compilation of from RAM-model programs? Because there are plenty of languages a TM can decide with zero additional memory. $\endgroup$
    – Raphael
    Jul 20, 2016 at 6:55
  • $\begingroup$ @Raphael No, we just don't want to focus on cases where the exact definition of the model could be very important. There are enough interesting things to say without having to worry whether some general reduction can be carried out in sublogarithmic space. $\endgroup$
    – Yuval Filmus
    Jul 20, 2016 at 7:13
  • 2
    $\begingroup$ If you want to study regular languages you don't need complexity theory. $\endgroup$
    – Yuval Filmus
    Jul 20, 2016 at 7:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.