PATH is NL-complete

A log space transducer is a Turing machine with a read-only input tape, a write-only output tape, and a read/write work tape. The head on the output tape cannot move leftward, so it cannot read what it has written. The work tape may contain  symbols. A log space transducer  computes a function where  is the string remaining on the output tape after  halts when it is started with  on its input tape. We call  a log space computable function.

Language  is log space reducible to language , written  if  is mapping reducible to  by means of a log space computable function .

A language  is NL-complete if

1.  and
2. every  in  is log space reducible to .

PATH is in NL

The NTM starting at node , nondeterministically guessing the nodes of a path from  to .

• The machine only records the position of the current node at each step on the work tape, not the entire path.

• The machine nondeterministically selects the next node from among those pointed by the current node,

• Repeat this action until it reaches node  and accepts. Or, until it has gone on for  steps and rejects, where  is the number of nodes in the graph.

PATH is NL-hard

Let's say that  decides  in  space. Given an input , we construct  in log space, where  is a directed graph that contains a path from  to  if and only if  accepts .

The nodes of  are the configurations of  on  For configurations  and  of  on  the pair  is an edge of  if  is one of the possible next configurations of  starting from  More precisely, if  's transition function indicates that  's state together with the tape symbols under its input and work tape heads can yield the next state and head actions to make  into  then  is an edge of  Node  is the start configuration of  on  Machine  is modified to have a unique accepting configuration, and we designate this configuration to be node .

This mapping reduces  to  because whenever  accepts its input, some branch of its computation accepts, which corresponds to a path from the start configuration  to the accepting configuration  in Conversely, if some path exists from  to  in  some computation branch accepts when  runs on input and  accepts .

To show that the reduction operates in log space, we give a log space transducer that outputs  on input  We describe  by listing its nodes and edges. Listing the nodes is easy because each node is a configuration of  on  nd can be represented in  space for some constant  The transducer sequentially goes through all possible strings of length  tests whether each is a legal configuration of  on  and outputs those that pass the test. The transducer lists the edges similarly. Log space is sufficient for verifying that a configuration  of  on  can yield configuration  because the transducer only needs to examine the actual tape contents under the head locations given in  to determine that  's transition function would give configuration  as a result. The transducer tries all pairs  in turn to find which qualify as edges of Those that do are added to the output tape.