# Proving $\#CYCLE \in \#P$

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.

• I'm not sure you understand what #P is. I suggest checking out the definition. – Yuval Filmus May 13 '17 at 18:42
• 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. – shinzou May 13 '17 at 18:55
• It's too bad they didn't give any example in class. – Yuval Filmus May 13 '17 at 18:56
• 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 – shinzou May 13 '17 at 18:58

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.