0
$\begingroup$

The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (You may use the fact that PATH is NL-complete.) PATH = {: G is a directed graph with a path from s to t}

My attempt: to show DCG is NL complete first we need to show it is in NL. then We need to show that PATH log space reduces to DCG. to show DCG is in NL we need to define a nondeterminstic Turing Machine that decides DCG in logn space. Here I have a question, what is n? The length of the string which encodes the graph? Can I think of it as if G has x vertices and y edges then the amount of things I can store in memory in the TM I define is log(x+y)? since Path is in NL let M1 be a nondeterministic TM which decides PATH in log space. define M2 (which decides DCG) as: given input for every pair of nodes (x,y) in G: run M1 on if M1 accepts (do nothing just continue the program) if M1 rejects then reject accept

M2 decides DCG, does it do so in logn space? I am guessing yes, because the only space we need is to keep track of what pairs of nodes we have gone through, but that could be represented as a single number if we are given an enumeration of all the pairs of nodes. Like if the enumeration was part of the encoding of the graph. But if our TM M2 has to store that enumeration then M2 doesnt use log space. M2 also uses space to run M1 on each pair, but M1 uses log space, and after each call to M1 we can forget/overwrite the space we used for running M1 on a previous pair.

now we want to show PATH log space reduces to DCG. We assume that there exists a deterministic TM M that decides DCG in log space. We want to use M to define a deterministic TM N which decides PATH in log space. Also given G,s,t we want to convert it into a graph G' such that G' is doubably connected (for every x and y in G' there is a path from x to y and a path from y to x) iff G has a path from s to t. Define G' as: the graph like G except, for every node x other than s and t, there is an edge from x to s, and an edge from t to x. Then G' is doubly connected iff there is a path from s to t in G. Define N as: given input run M on G' if M accepts then accept, if M rejects then reject

then N decides PATH. Does it do so in log space? M only uses log space, but perhaps there are too many edges in G' so that storing G' uses too much space

If I made any mistakes please correct me. Any additional feedback is very appreciated. In particular, helping me understand some of those questions I had about the space usage. Also I am looking for a tutor in this subject. We could perhaps discuss questions over facebook or something, and I send the money over e-transfer or something.

$\endgroup$
  • $\begingroup$ Logspace means "there is a constant $c$ such that the space used is at most $c\log n$ bits, where $n$ is the instance size in bits". The constant can be 2, or 20000, or whatever, as long as it works for all instance sizes. $\endgroup$ – András Salamon Mar 28 '18 at 13:37
  • $\begingroup$ Please don't use the 'Your Answer' box to ask follow-up questions. It should be reserved only for material that directly answers the question that was asked. $\endgroup$ – D.W. Mar 28 '18 at 21:04
  • $\begingroup$ It looks like you created two separate accounts. You might want to merge them. If you create an account and a password, that will give you the ability to post comments and revise your question. $\endgroup$ – D.W. Mar 28 '18 at 21:05
  • $\begingroup$ This site is for specific, answerable technical questions. Open-ended requests for feedback are not a good fit here. We discourage 'Please check whether my work is correct', as such questions are usually not interesting to others. Requests for tutoring are off-topic here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$ – D.W. Mar 28 '18 at 21:07

Your Answer

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

Browse other questions tagged or ask your own question.