patternMinor
STCON is NL complete - but why is the reduction in L?
Viewed 0 times
whythebutcompletereductionstcon
Problem
I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity
I understand the reduction, but how is it logspace?
I understand each state is of $O(\log(n))$ space. What I don't understand is how I can create the graph in logspace.
I tried to do some kind of DFS, but remembering the states looks like it'd take $\log(n) * \log(n)$ because the longest path is $\log(n)$ and it costs $\log(n)$ to remember each one?
EDIT: to make sure, I do understand the why the language is in NL, but I don't understand how the reduction from lanuage L in NL to STCON is logspace.
I understand the reduction, but how is it logspace?
I understand each state is of $O(\log(n))$ space. What I don't understand is how I can create the graph in logspace.
I tried to do some kind of DFS, but remembering the states looks like it'd take $\log(n) * \log(n)$ because the longest path is $\log(n)$ and it costs $\log(n)$ to remember each one?
EDIT: to make sure, I do understand the why the language is in NL, but I don't understand how the reduction from lanuage L in NL to STCON is logspace.
Solution
You don't need to do DFS. Each branch on the nondeterministic TM corresponds to each possible path from $s$ to any node $v$ of length at most $n$. You also maintain the index of the vertex it is at which takes $O(\log{n})$ space. If at some step the NDTM has reached the node $t$ then you it halts with ACCEPT. If the NDTM has checked $n$ nodes and it has not reached the node $t$ then it REJECTs. So, if $t$ is reachable from $s$ then there is a path from $s$ to $t$ which would correspond to some branch on the NDTM. In this case the NDTM will halt with ACCEPT.
In simple words, each branch of computation needs to maintain a constant number of variables of size $\log n$: current node, counter for number nodes explored so far, etc. We don't care which nodes we have visited, the only thing we care about is the current node and the number of nodes we have visited in order to stop as soon as we visit $n$ nodes (all nodes).
In order to prove that STCON is NL-complete, given a string $w$ we need to convert it into STCON instance using log-space. Let $M$ be a log-space NDTM accepting $L$. We convert the configurations of computation of $M$ on $w$ into a directed graph. Each node corresponds to a single configuration and if there is a legal transition from a configuration $C_{i}$ into a configuration $C_j$ there is an edge between $C_{i}$ and $C_j$. The size of each configuration is $O(\log{|w|})$ since $M$ computes using $O(\log{|w|})$ space. Generating all possible configurations (nodes) and verifying that $C_i$ yields $C_j$, i.e., adding edge, take $O(\log{|w|})$ space.
Note also that we could generate all possible nodes/configurations of length $\log{|w|}$ by going through all possible strings of length $\log{|w|}$ and test if the generated string is a legal configuration. If it is legal then the TM writes it to its output tape. All this is done in $O(\log{|w|})$ space. Similarly you could generate all pairs $(C_i, C_j)$ and check if $C_i$ yields $C_j$. If $C_i$ yields $C_j$ then write it to the output tape as an edge of the output graph. This also takes $O(\log{|w|})$ space.
The key thing is that you don't need to worry about the time complexity whether it takes linear or exponential time. The output space isn't restricted to $O(\log{|w|})$ space either. Once you convert $w$ to an instance of STCON problem, STCON can decide if this instance belongs to $L_{STCON}$.
In simple words, each branch of computation needs to maintain a constant number of variables of size $\log n$: current node, counter for number nodes explored so far, etc. We don't care which nodes we have visited, the only thing we care about is the current node and the number of nodes we have visited in order to stop as soon as we visit $n$ nodes (all nodes).
In order to prove that STCON is NL-complete, given a string $w$ we need to convert it into STCON instance using log-space. Let $M$ be a log-space NDTM accepting $L$. We convert the configurations of computation of $M$ on $w$ into a directed graph. Each node corresponds to a single configuration and if there is a legal transition from a configuration $C_{i}$ into a configuration $C_j$ there is an edge between $C_{i}$ and $C_j$. The size of each configuration is $O(\log{|w|})$ since $M$ computes using $O(\log{|w|})$ space. Generating all possible configurations (nodes) and verifying that $C_i$ yields $C_j$, i.e., adding edge, take $O(\log{|w|})$ space.
Note also that we could generate all possible nodes/configurations of length $\log{|w|}$ by going through all possible strings of length $\log{|w|}$ and test if the generated string is a legal configuration. If it is legal then the TM writes it to its output tape. All this is done in $O(\log{|w|})$ space. Similarly you could generate all pairs $(C_i, C_j)$ and check if $C_i$ yields $C_j$. If $C_i$ yields $C_j$ then write it to the output tape as an edge of the output graph. This also takes $O(\log{|w|})$ space.
The key thing is that you don't need to worry about the time complexity whether it takes linear or exponential time. The output space isn't restricted to $O(\log{|w|})$ space either. Once you convert $w$ to an instance of STCON problem, STCON can decide if this instance belongs to $L_{STCON}$.
Context
StackExchange Computer Science Q#81306, answer score: 2
Revisions (0)
No revisions yet.