2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ I think you proved that the language is in NL? I understand that, what I don't understand is why the reduction from a language L in NL to STCON is in logspace. $\endgroup$ – Gray Sep 17 '17 at 17:47
  • $\begingroup$ Did you read a proof of NL-completeness of STCON? For example, both Sipser's and Arora's textbooks provide proofs. What part didn't you understand? The proof are based on computation history (or computation configurations). $\endgroup$ – fade2black Sep 17 '17 at 18:15
  • $\begingroup$ From the wikipedia proof I linked : " Map all possible states of the deterministic log-space machine to vertices of a graph, and put an edge between u and v if the state v can be reached from u within one step of the non-deterministic machine." , From the part about it being NP hard. $\endgroup$ – Gray Sep 17 '17 at 18:44
  • $\begingroup$ I get the idea. But how exactly we do find all the states (configurations) of the machine? $\endgroup$ – Gray Sep 17 '17 at 18:45
  • $\begingroup$ Generating all possible configurations (nodes) in $O(log|w|)$ - this is the only part I don't understand how to do in the required complexity. thanks $\endgroup$ – Gray Sep 18 '17 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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