|
Abstract : |
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, |
