[Computational Complexity] 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.
Posted by Lance to Computational Complexity at 3/30/2005 07:02:00 PM