License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1363
URN: urn:nbn:de:0030-drops-13636
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1363/
Go to the corresponding LIPIcs Volume Portal

Kinne, Jeff ; van Melkebeek, Dieter

Space Hierarchy Results for Randomized Models

pdf-format:
22011.KinneJeff.Paper.1363.pdf (0.2 MB)

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.


BibTeX - Entry

@InProceedings{kinne_et_al:LIPIcs:2008:1363,
  author =	{Jeff Kinne and Dieter van Melkebeek},
  title =	{{Space Hierarchy Results for Randomized Models}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{433--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1363},
  URN =		{urn:nbn:de:0030-drops-13636},
  doi =		{10.4230/LIPIcs.STACS.2008.1363},
  annote =	{Keywords: Computations with Advice, Space Hierarchy, Randomized Machine, Promise Classes, Semantic Models}
}

Keywords: Computations with Advice, Space Hierarchy, Randomized Machine, Promise Classes, Semantic Models
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI