Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  David Richerby Feb 23 at 21:05

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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