8
$\begingroup$

In Savitch's 1969 paper, "Relationships Between Nondeterministic and Deterministic Tape Complexities", he states that "all common storage functions L(n) >= lg n are measurable. In particular, any polynomial in n and lg n is measurable." His definition of measurable is: "A function L(n) is said to be measurable if there is some Turing machine with just one storage tape such that, given any input of length n, the machine will halt after a computation in which the storage tape head scans exactly L(n) squares."

So, my problem is, based on his definition, I don't understand why storage functions L(n) >= lg n would be measurable, while functions L(n) < lg n would not be. Is this somehow implicit in his definition? Or are there some publications that I should read?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

I think that this definition is nowadays known under the term space-constructible function. There are functions in sublogarithmic space that are space constructible, while others are not.

http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: There are no fully space constructible functions between log log n and log n. Information Processing Letters 24(6),361-362.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Great! I'll give that paper a read. Thank you, Hermann. $\endgroup$
    – djkern
    Oct 14, 2012 at 19:10

Your Answer

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

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