DCG = { G | Directed graphs that contains a cycle }

How can I proof that DCG belongs to NL?

  • $\begingroup$ Are you familiar with en.wikipedia.org/wiki/St-connectivity? $\endgroup$ – D.W. Nov 18 '19 at 3:11
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Nov 18 '19 at 3:12