Space Hierarchy Results for Randomized and Other Semantic Models Download as PDF


We prove space hierarchy and separation results for randomized and other semantic models of computation with advice where a machine is only required to behave appropriately when given the correct advice sequence. 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 deal with space-bounded randomized machines that always halt, and read as follows. Let s(n) be any space-constructible monotone function that is Ω(log n) and let s'(n) be any function such that s'(n) = ω(s(n+as(n))) for all constants a.

If, in addition, s(n) = O(n) then the condition on s' above can be relaxed to s'(n) = ω(s(n+1)). This yields tight space hierarchies for typical space bounds s(n) that are at most linear.

We also obtain results that apply to generic semantic models of computation.