0
$\begingroup$

I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\#CYCLE \in \#P$, if I could represent a distinct cycle, then I'll have a witness.

I saw this question: Number of cycles in a graph? they mention the reduction from HAM #CYCLE in Counting Complexity by Arora and Barak, but I don't understand how does that help.

You have some directed graph, no one said it has a hamilton cycle, and the gadget doesn't return how many cycles there in the graph or a way to distinguish between them, it just makes all the cycles longer.

So instead, is it possible to use a topological sort to count cycles? since it can detect every cycle, we can use it to distinguish between them.

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm not sure you understand what #P is. I suggest checking out the definition. $\endgroup$
    – Yuval Filmus
    Commented May 13, 2017 at 18:42
  • $\begingroup$ I have the definition in front of me: The class of functions $f:\{0,1\}^* \to\{0,1\}^*$ that have a poly time TM M, polynom p such that $\forall x \in \{0,1\}^*$ $f(x)=|\{y∈\{0,1\}^{p(|x|)} .M(x,y)=1\}|$, I don't see how does that help in proving a problem is in #P. $\endgroup$
    – shinzou
    Commented May 13, 2017 at 18:55
  • $\begingroup$ It's too bad they didn't give any example in class. $\endgroup$
    – Yuval Filmus
    Commented May 13, 2017 at 18:56
  • $\begingroup$ They didn't, and I can't find any example online, closest example I found just said: "it's easy to see that #SAT is in #P"... @YuvalFilmus $\endgroup$
    – shinzou
    Commented May 13, 2017 at 18:58

1 Answer 1

Reset to default
3
$\begingroup$

The class #P consists of those functions $f$ such that there is a polytime relation $R$ and a polynomial bound $p$ satisfying $$ f(x) = |\{ |y| < p(|x|) : R(x,y) \}|. $$ In words, if we think of $y$ as a "witness" for $x$, then $f(x)$ should count the number of witnesses for $x$. For example, if $R(x,y)$ is the relation that $y$ is a cycle in the graph $x$, then (if you're careful enough) $f(x)$ will count the number of cycles in the graph $x$. You need to be a bit careful to count each cycle exactly once.

Improve this answer
$\endgroup$
6
  • $\begingroup$ That's it? no need to describe a way to represent a unique cycle as a witness? $\endgroup$
    – shinzou
    Commented May 13, 2017 at 18:48
  • $\begingroup$ I did mention twice that you have to be careful. Since it's your exercise rather than mine, I won't be posting a complete solution. $\endgroup$
    – Yuval Filmus
    Commented May 13, 2017 at 18:52
  • $\begingroup$ What's left is finding a bijection between the cycles and binary strings? $\endgroup$
    – shinzou
    Commented May 14, 2017 at 17:27
  • $\begingroup$ Yes, this is what remains to be done. $\endgroup$
    – Yuval Filmus
    Commented May 14, 2017 at 17:37
  • 1
    $\begingroup$ Unfortunately I cannot act as your TA. $\endgroup$
    – Yuval Filmus
    Commented May 14, 2017 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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