Gap-Languages and Log-Time Complexity Classes

This paper shows that classical results about complexity classes involving "delayed diagonalization" and "gap languages," such as Ladner's Theorem and Schoning's Theorem and independence results of a kind noted by Schoning and Hartmanis, apply at very low levels of complexity, indeed all the way down in Sipser's log-time hierarchy. This paper also investigates refinements of Sipser's classes and notions of log-time reductions, following on from recent work by Cai, Chen, and others. 1 Introduction Many theorems about the structure of familiar complexity classes such as P, NP, and PSPACE have been obtained by a technique called delayed diagonalization [Lad75, CM81, Sch82, MY85, Amb85a] (see also [BDG88]). For instance, there are languages E in PSPACE such that E is not in LOGSPACE and E is not PSPACE-complete under log-space reductions ( log m ). Moreover, the structure of such languages E under log m embeds all countable partial orders. On hypothesis NP 6= P, there is a similar ric..