ECCC-Report TR04-014https://eccc.weizmann.ac.il/report/2004/014Comments and Revisions published for TR04-014en-usMon, 16 Feb 2004 13:41:04 +0200
Paper TR04-014
| Languages to diagonalize against advice classes |
Chris Pollett
https://eccc.weizmann.ac.il/report/2004/014Variants 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.
Mon, 16 Feb 2004 13:41:04 +0200https://eccc.weizmann.ac.il/report/2004/014