10.4230/LIPICS.STACS.2008.1363
Kinne, Jeff
Jeff
Kinne
van Melkebeek, Dieter
Dieter
van Melkebeek
Space Hierarchy Results for Randomized Models
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Computations with Advice
Space Hierarchy
Randomized Machine
Promise Classes
Semantic Models
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13636
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
38
433
444
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
164460 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 433-444