Under the auspices of the Computational Complexity Foundation (CCF)

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