1
$\begingroup$

In the chapter on space complexity in "Computational Complexity: A conceptual perspective" by Goldreich, it is stated (ch 5.1.2, p 146):

It is tempting to say that sub-logarithmic space machines are not more useful than constant space machines, because it seems impossible to allocate a sub-logarithmic amount of space. This wrong intuition is based on the presumption that the allocation of a nonconstant amount of space requires explicitly computing the length of the input, which in turn requires logarithmic space. However, this presumption is wrong: The input itself (in case it is of a proper form) can be used to determine its length (and/or the allowed amount of space)

It then goes on to say that not DSPACE(O(1)) = DSPACE(O(log(n))) as this wrong intuition would let us believe, but rather DSPACE(O(1)) = DSPACE(O(log(log(n)))), I think because we can encode the input length in the input itself.

However, I don't understand what this paragraph is even about in the first place. E.g. what does "allocating" space resources even have to do with space complexity? Most algorithms I know don't "allocate" any space resources, they just use it, and they don't need to know the length of the input explicitly. E.g. to add two integers, we can just start adding the final bits together, taking over the carry, and so forth. We don't first "compute the length of the input".

Could someone explain why we would need to "allocate" space, and thus why either DSPACE(O(1)) = DSPACE(O(log(n))) or DSPACE(O(1)) = DSPACE(O(log(log(n)))) is even plausible in principle?

$\endgroup$
4
  • $\begingroup$ @YvesDaoust, yeah I assume it is a language shortcut, but I still don't get what the paragraph is even about. To be clear, I mean that I have no idea whatsoever why an algorithm needs to "know the length of the input" or why anyone would have the described intution. So I think my question is very basic. $\endgroup$
    – user56834
    Aug 3, 2022 at 8:27
  • $\begingroup$ @YvesDaoust, it says the allocation of nonconstant memory doesn't require explicitly computing the length of the input, because the input can be used to determine its length. My confusion is why the algorithm needs to know the length of the input at all, and why this is even a point that is at all relevant to minimal amount of useful space. $\endgroup$
    – user56834
    Aug 3, 2022 at 11:54
  • $\begingroup$ @YvesDaoust, "Come on", well you may not believe me, but I still genuinely don't understand this, and your comment doesn't clarify it for me. (note, your comment is about linear time, but my question is about space complexity, not time complexity). $\endgroup$
    – user56834
    Aug 3, 2022 at 14:33
  • $\begingroup$ I don't think this is going anywhere so I'll just wait for an answer. Just note that I get that for some particular problems we might need to know the length of the input, but the claim being made by the textbook is a universal one: having increasing but less than logarithmic space doesn't provide any benefit over just having constant space, for ANY problem. $\endgroup$
    – user56834
    Aug 3, 2022 at 19:54

1 Answer 1

2
$\begingroup$

Most algorithms I know don't "allocate" any space resources, they just use it, and they don't need to know the length of the input explicitly

The statement that "Most algorithms I know don't 'allocate' any space resources, they just use it" is red herring, since most algorithms use space beyond input and output.

  • Without space beyond read-only input and write-only output, an algorithm is equivalent to a finite state machine.
  • Without space beyond readable-and-writable input and write-only output, an algorithm is equivalent to a linear bounded automaton.

Note that we, or the book Computational Complexity: A conceptual perspective by Goldreich considers the space beyond input and output must have been allocated in this discussion, whether implicitly (as "they just use it") or explicitly (such as described below).

How do most algorithm "allocate" space? Or, in equivalent terms, how do most algorithm find and use space other than the input and output?

Let us ignore the algorithms that "allocate" $O(1)$ auxiliary space, since they are irrelevant to this investigation.

Let us consider the algorithm that "allocate" more than $O(1)$ auxiliary space, i.e., some space whose size is not bounded by a constant. In other words, we are considering dynamic memory allocation.

In the model of Turing machines explicit memory allocation is rarely seen, since a Turing machine enjoys unbounded memory by definition. Extra memory will be used by an algorithm as they become needed. (However, "extra memory" used implies none other than memory allocation.)

Hence, the initial (correct or wrong) intuition for memory usage pattern does not come from the descriptions of algorithms by Turing machines. Instead, those intuition come mostly from people writing programs in pseudocode, c/c++ that deal with memory allocation explicitly.

A dynamic memory allocation requires a size as a parameter. This size should not be a constant; otherwise, we can use static memory allocation.

How does a variable size arise? One of the most common variables that come from input is the length of the input. So it is natural that a variable size might be computed from the length of the input.

  • For example, allocate an array that is as large as the input array as the working space to sort the input array.
  • For example, allocate an array of size that is the same as the number of given edges to track whether edges have been visited or not.
  • (May I say there are too many examples...)

Hence, Goldreich refers to "the allocation of a nonconstant amount of space" that "requires explicitly computing the length of the input" as a natural "presumption". Or so I understand.

Of course, we should mention, as Goldreich pointed out, that intuition is wrong.

$\endgroup$
3
  • $\begingroup$ I am not basing this on intuitions from high level programming languages. If you run a basic addition algoeithm on a turig machine, I dont see when you ever need to actually know and store in short term memory the size of the input. (In fact you don't, because addition has constant working memory usage, so this doesnt contradict what the textbook is saying. It's just that I don't know what the abstract argument is for why variable memory size requires atoring the size of the input or something in memory.) I'm looking for an answer more in terms of theoretical cs (turing machines) than $\endgroup$
    – user56834
    Aug 6, 2022 at 7:48
  • $\begingroup$ Than a handwavy atory about high level peogramming languages. $\endgroup$
    – user56834
    Aug 6, 2022 at 7:49
  • $\begingroup$ Good point. Please check my updated answer. Note that an answer that finds the origin/reason of the intuition hereof from the usual theory and practice of Turing machines is probably wrong. $\endgroup$
    – John L.
    Aug 6, 2022 at 10:31

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.