Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-014 | 26th November 2003 00:00

Languages to diagonalize against advice classes

RSS-Feed




TR04-014
Authors: Chris Pollett
Publication: 16th February 2004 13:41
Downloads: 2951
Keywords: 


Abstract:

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 contain $\PSPACE$,
uniform $\TC^0/n^k$ does not contain $\CH$, and uniform $\ACC/n^k$
does not contain $\ModPH$. Consequences for selective sets are also
obtained. In particular, it is shown that
$\R^{DTIME(n^k)}_T(\NP$-$\sel)$ does not contain $\PTIME^{\NE}$,
$\R^{DTIME(n^k)}_T(\PTIME$-$\sel)$ does not contain $\EXP$, and
that $\R^{DTIME(n^k)}_T(\L$-$\sel)$ does not contain $\PSPACE$.
Finally, a circuit size hierarchy theorem is established.



ISSN 1433-8092 | Imprint