Wednesday, March 30, 2005

Sublogarithmic Space

A reader asks
I wanted to ask you something about the Savitch and Immerman-Szelepcsényi theorems that I saw you have in your weblog. In both thorems we have that s(n)≥logn. Why is that?
For any space function s(n), we also need to have a pointer to read every bit of the input and thus we'll have n2O(s(n)) possible configurations. For s(n)≥log n, we can safely ignore the extra factor of n but for s(n)=o(log n) this causes problems for directly using the proofs of Savitch and Immerman and Szelepcsényi.

Still many researchers have studied sublogarithmic space classes but these results tend to be dependent on the exact machine model and it's tricky to understand what they tell us about general computation.

3 comments:

  1. Does this relate somehow of the new Berkeley result?

    ReplyDelete
  2. What's the "new Berkeley result"?

    ReplyDelete
  3. Yes, what new Berkeley result? I am always the last one to know.

    Luca

    ReplyDelete