Revision #1 Authors: Jeff Kinne, Dieter van Melkebeek

Accepted on: 12th December 2008 00:00

Downloads: 1559

Keywords:

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 \Omega(log n) and let s'(n) be any function such that s'(n) = \omega(s(n+as(n))) for all constants a.

(1) 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 machines using s(n) space and min(s(n),n) bits of advice.

(2) 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.

If, in addition, s(n) = O(n) then the condition on s' above can be relaxed to s'(n) = \omega(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.

TR07-134 Authors: Jeff Kinne, Dieter van Melkebeek

Publication: 17th December 2007 16:33

Downloads: 1402

Keywords:

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

* There exists a language computable by <i>two-sided</i> error randomized machines using <i>s</i>'(<i>n</i>) space and one bit of advice that is not computable by <i>two-sided</i> error randomized machines using <i>s</i>(<i>n</i>) space and min(<i>s</i>(<i>n</i>),<i>n</i>) bits of advice.

* There exists a language computable by <i>zero-sided</i> error randomized machines in space <i>s</i>'(<i>n</i>) with one bit of advice that is not computable by <i>one-sided</i> error randomized machines using <i>s</i>(<i>n</i>) space and min(<i>s</i>(<i>n</i>),<i>n</i>) bits of advice.

The condition that <i>s</i>(<i>a n</i>) = O(<i>s</i>(<i>n</i>)) 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.