Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOMIZED MACHINES:
Reports tagged with Randomized Machines:
TR05-111 | 3rd October 2005
Dieter van Melkebeek, Konstantin Pervyshev

A Generic Time Hierarchy for Semantic Models With One Bit of Advice

We show that for any reasonable semantic model of computation and for
any positive integer $a$ and rationals $1 \leq c < d$, there exists a language
computable in time $n^d$ with $a$ bits of advice but not in time $n^c$
with $a$ bits of advice. A semantic ... more >>>




ISSN 1433-8092 | Imprint