Is L closed under linear-time reductions?

Question

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.

Answer 1

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