patternMinor
Is L closed under linear-time reductions?
Viewed 0 times
linearclosedtimeunderreductions
Problem
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?
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.
Solution
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
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
Context
StackExchange Computer Science Q#44259, answer score: 2
Revisions (0)
No revisions yet.