Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ADVICE CLASSES:
Reports tagged with advice classes:
TR04-014 | 26th November 2003
Chris Pollett

Languages to diagonalize against advice classes

Variants of Kannan's Theorem are given where the circuits of
the original theorem are replaced by arbitrary recursively presentable
classes of languages that use advice strings and satisfy certain mild
conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$
does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does
not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not ... more >>>




ISSN 1433-8092 | Imprint