4
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

Your Answer

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

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