GAP-LANGUAGES AND LOG-TIME COMPLEXITY CLASSES

This paper shows that classical results about complexity classes invol ving ''delayed diagonalization'' and ''gap languages'', such as Ladner 's Theorem and Schoning's Theorem and independence results of a kind n oted by Schoning and Hartmanis, apply at very low levels of complexity , indeed all the way down in Sipser's log-time hierarchy. This paper a lso investigates refinements of Sipser's classes and notions of log-ti me reductions, following on from recent work by Cai, Chen, and others.