Space Hierarchy Results for Randomized Models

Abstract

We prove space hierarchy and separation results for randomized and
   other semantic models of computation with advice.  Previous works
   on hierarchy and separation theorems for such models focused on
   time as the resource.  We obtain tighter results with space as the
   resource.  Our main theorems are the following.  Let $s(n)$ be any
   space-constructible function that is $Omega(log n)$ and such that
   $s(a n) = O(s(n))$ for all constants $a$, and let $s'(n)$ be any
   function that is $omega(s(n))$.
   
   - There exists a language computable by two-sided error randomized
   machines using $s'(n)$ space and one bit of advice that is not
   computable by two-sided error randomized machines using $s(n)$
   space and $min(s(n),n)$ bits of advice.
   
   - There exists a language computable by zero-sided error randomized
   machines in space $s'(n)$ with one bit of advice that is not
   computable by one-sided error randomized machines using $s(n)$
   space and $min(s(n),n)$ bits of advice.
   
   The condition that $s(a n)=O(s(n))$ is a technical condition
   satisfied by typical space bounds that are at most linear.  We also
   obtain weaker results that apply to generic semantic models of
   computation.