<p>This is one of the problems (very briefly) discussed by Valiant, "The Complexity of Enumeration and Reliability Problems", <em>SIAM J. Comput.</em> 1979, doi:10.1137/0208032. See the mention of "elementary cycles" near the top of p. 417. Valiant gives a Turing reduction from the number of Hamiltonian cycles.</p>

CC BY-SA 3.0
2017-05-05T21:39:33.713Z
2017-05-05T21:39:33.713Z
David Eppstein
<p>We know that #SAT is #P-complete. We also know that problems with polynomial decision versions like PERMANENT are #P-complete. Is it true that finding the number of simple cycles in a graph, i.e. #CYCLE is also #P-complete? This is also a problem with decision version solved in polynomial time.</p>

<p>I suppose that it is either not-known or false, because it might be used a a popular example in textbooks like Arora and Barak's book, etc. </p>

<cc.complexity-theory><counting-complexity><permanent>
Is #CYCLE #P-complete?
sdd
# Is #CYCLE #P-complete?

(Asked by: username_0 on 2017-05-05)

We know that #SAT is #P-complete. We also know that problems with polynomial decision versions like PERMANENT are #P-complete. Is it true that finding the number of simple cycles in a graph, i.e. #CYCLE is also #P-complete? This is also a problem with decision version solved in polynomial time.

I suppose that it is either not-known or false, because it might be used a a popular example in textbooks like Arora and Barak's book, etc.

**Tags:** cc.complexity-theory, counting-complexity, permanent

---

## 1 answers

### Answer by username_1 on 2017-05-05. Score: 8

This is one of the problems (very briefly) discussed by Valiant, "The Complexity of Enumeration and Reliability Problems", *SIAM J. Comput.* 1979, doi:10.1137/0208032. See the mention of "elementary cycles" near the top of p. 417. Valiant gives a Turing reduction from the number of Hamiltonian cycles.


---

