5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! That turned out to be more subtle than I anticipated. $\endgroup$ – András Salamon Jul 10 '15 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.