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.