caa a22 4500 46790975X CHVBK 20180406152846.0 cr unu---uuuuu 170328e20060301xx s 000 0 eng 10.1007/s00037-005-0202-1 doi (NATIONALLICENCE)springer-10.1007/s00037-005-0202-1 Pollett Chris Department of Computer Science, San Jose State University, 214 MacQuarrie Hall, One Washington Square, 95192, San Jose, CA, USA aut Languages to diagonalize against advice classes [Elektronische Daten] [Chris Pollett] 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. Let polyk denote those functions in O(nk). These variants imply that $$\mathsf{DTIME}(n^{k})^{\mathsf{NE}}/\mathsf{poly} _{k}$$ does not contain $$\mathsf{P}^{\mathsf{NE}},\;\mathsf{DTIME}\left(2^{n^{k'}}\right)/\mathsf{poly}_{k}$$ does not contain $$\mathsf{EXP},\;\mathsf{SPACE}\left(n^{k'}\right)/\mathsf{poly}_{k}$$ does not contain PSPACE, uniform TC0/polyk does not contain CH, and uniform ACC/polyk does not contain ModPH. Consequences for selective sets are also obtained. In particular, it is shown that $$\mathsf{R}_{T}^{\mathsf{DTIME}(n^{k})}(\mathsf{NP}\hbox{-}\mathsf{sel})$$ does not contain $$\mathsf{P}^{\mathsf{NE}},\;\mathsf{R}_{T}^{\mathsf{DTIME}(n^{k})}(\mathsf{P}\hbox{-}\mathsf{sel})$$ does not contain EXP, and $$\mathsf{R}_{T}^{\mathsf{DTIME}(n^{k})}(\mathsf{L}\hbox{-}\mathsf{sel})$$ does not contain PSPACE. Finally, a circuit size hierarchy theorem is established. Birkhäuser Verlag, Basel, 2005 Advice classes nationallicence EXP nationallicence NEXP nationallicence NE nationallicence CH nationallicence ModPH nationallicence p-selective nationallicence complexity classes nationallicence nonuniform computation nationallicence 68Q15 nationallicence 03D15 nationallicence computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 341-361 1016-3328 14:4<341 2006 14 37 https://doi.org/10.1007/s00037-005-0202-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-005-0202-1 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Pollett Chris Department of Computer Science, San Jose State University, 214 MacQuarrie Hall, One Washington Square, 95192, San Jose, CA, USA aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 341-361 1016-3328 14:4<341 2006 14 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer