Log-space transducer explained

In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions.

A log space transducer,

M

, has three tapes:

O(logn)

symbols).

M

will be designed to compute a log-space computable function

f\colon\Sigma\ast\Sigma\ast

(where

\Sigma

is the alphabet of both the input and output tapes). If

M

is executed with

w

on its input tape, when the machine halts, it will have

f(w)

remaining on its output tape.

A language

A\subseteq\Sigma\ast

is said to be log-space reducible to a language

B\subseteq\Sigma\ast

if there exists a log-space computable function

f

that will convert an input from problem

A

into an input to problem

B

in such a way that

w\inA\ifff(w)\inB

.

This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction:

  1. The property of transitivity holds. (A reduces to B and B reduces to C implies A reduces to C).
  2. If A reduces to B, and B is in L, then we know A is in L.

Transitivity holds because it is possible to feed the output tape of one reducer (A→B) to another (B→C). At first glance, this seems incorrect because the A→C reducer needs to store the output tape from the A→B reducer onto the work tape in order to feed it into the B→C reducer, but this is not true. Each time the B→C reducer needs to access its input tape, the A→C reducer can re-run the A→B reducer, and so the output of the A→B reducer never needs to be stored entirely at once.

References