__
TR04-014 | 26th November 2003 00:00
__

#### Languages to diagonalize against advice classes

**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.