Computational Complexity

Wednesday, March 30, 2005

 
Sublogarithmic Space

Posted by Lance

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 n2^O(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.

7:02 PM #

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

   4:15 PM, March 31, 2005

2.  Anonymous says:  
   
   What's the "new Berkeley result"?
   

   6:55 PM, March 31, 2005

3.  Anonymous says:  
   
   Yes, what new Berkeley result? I am always the last one to know.
   
   Luca
   

   10:30 PM, March 31, 2005

Comment Feeds: This Post All