7
$\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

$\endgroup$
  • 1
    $\begingroup$ Arora has a coauthor. $\endgroup$ – Yuval Filmus Jul 20 '16 at 6:40
  • $\begingroup$ @YuvalFilmus, I've fixed that. Thanks. $\endgroup$ – Fawzy Hegab Jul 20 '16 at 20:12
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.)

$\endgroup$
  • $\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 '16 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 '16 at 7:13
  • 2
    $\begingroup$ If you want to study regular languages you don't need complexity theory. $\endgroup$ – Yuval Filmus Jul 20 '16 at 7:14

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.