I know that a logspace transducer is a deterministic Turing machine that enables us to use log-space complexity. I do not understand though why that is correct. Whatever algorithms can be implemented in that machine are automatically of log-space complexity? Why is that?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The definition of "log-space complexity" is that the problem can be solved by a deterministic Turing machine that uses logarithmic space; the definition of a log-space transducer is that it's a Turing machine that uses logarithmic space. $\endgroup$– David RicherbyFeb 23, 2014 at 21:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A logspace transducer is a function which can be computation in logarithmic space (in terms of input size). This is just the definition. One important property of logspace transducers is that the composition of two logspace transducers is another logspace transducer; this is not as trivial as it looks.
P-completeness is defined with respect to logspace reductions. In other words, the many-one reductions considered are logspace transducers. Compare this with the definition of NP-completeness, in which the many-one reductions are polytime. The reason we have to restrict the power of the reductions (from polytime to logspace) is that every problem in P is trivially P-complete with respect to polytime reductions (exercise).
The composition property of logspace transducers is important for the following theorem: if $L$ is P-complete and $L$ reduces to $M$, then $M$ is P-complete. If you follow the proof carefully, you will see that it is crucial that the composition of two logspace transducers is another logspace transducer.
answered Feb 23, 2014 at 20:28