Space Hierarchy Results for Randomized Models

Jeff will be presenting this research at STACS shortly. This will be a practice for that presentation in the same format as the STACS presentation - 20 minutes and aimed at a general theory audience. All are welcome to attend, and comments afterwards will be much appreciated.

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 Ω(log n) and such that s(a n) = O(s(n)) for all constants a, and let s'(n) be any function that is ω(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.