L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace.Is L closed under linear-time reductions?It is possible that for some pair of languages Q and R, every linear-time reduction from Q to R requires more than logarithmic space.Up to linear space could be used while still remaining within linear time.So it isn't immediately obvious to me that L must be closed under linear-time reductions.On the other hand, it is not clear what a counterexample would look like.One wants a language Q that can be linear-time many-one reduced to a language in L (for instance, to undirected graph st-connectivity), yet so that Q is not in L.
Is L closed under linear-time reductions?
complexity theory;reductions;complexity classes;space complexity
L is closed under linear-time reductions if and only if L = P.Proof:If L is closed under linear-time many-one reductions then:Since L has non-trivial problems, all problems that are solvable linear time are in L.Let (x) be the modification of the most basic P-complete problem to ask about the first sqrt(T) steps rather than the first T steps. Since unary-to-binary conversion can be done in linear time and [square-roots can be computed and TMs can be simulated in quasi-linear time], (x) can be solved in linear time. Since L has non-trivial problems, there is a linear-time many-one reduction from (x) to a problem in L. By this paragraph's assumption, that means (x) is in L.  Since L can square unary inputs, there is a logspace reduction from the most basic P-complete problem to (x). Thus (x) is P-complete. Since (x) is in L, that means  P  L .If L is closed under linear-time many-one reductions then then P  L. With no assumptions, L  P.  Therefore, if L is closed under linear-time many-one reductions then then L = P. Since P can perform linear-time Turing reductions, P is closed under linear-time Turing reductions. Therefore, if L = P  then L is closed under linear-time Turing reductions.  QED