4
$\begingroup$

Thanks for the comments, I refined the question.

What is the complexity relationship between counting and enumeration problems? If a counting problem is #P-complete, it means that the enumeration version is #P-hard.

How about problems that can be solved in polynomial time? For example, do counting triangles and enumerating triangles in a graph have the same complexity lower/upper bound?

More specifically,

Given an algorithm that can solve the counting problem in $O(f(n))$ time, can we also solve the corresponding enumeration problem in $O(f(n))$ time? Assume that the output size of enumeration problem is $O(f(n))$ or somehow can be compressed using $O(f(n))$ storage.

For example, we may use cliques instead of triangles to represent the output results of triangle enumeration to reduce the output size. It may be not an appropriate example since it may not reduce the worst case space complexity. But for some enumeration problems, I think it may be possible.

Could anyone give any explanations or references?

$\endgroup$
  • 4
    $\begingroup$ Enumerating solutions might require much more time than counting the number of solutions. For example, counting the number of permutations on $n$ elements is trivial (there are $n!$ permutations) but enumerating all of them requires time $n!$. The number of triangles in a graph can be computed in time $O(n^{\omega})$; enumerating all triangles requires time $\Omega(n^3)$ in the worst case. $\endgroup$ – Yury Sep 6 '13 at 1:33
  • 2
    $\begingroup$ @Yury For enumeration algorithms, people normally talk about the time to produce the first output and the time between successive outputs, for the reason you highlight. The only reason permutations take a long time to enumerate is that there's a lot of them; the individual permutations aren't hard to find. In contrast, 3-SAT solutions take a long time to enumerate because it's hard to find even one. $\endgroup$ – David Richerby Sep 6 '13 at 6:55
  • 1
    $\begingroup$ @David, that is not clear from the question, rather it seems that is not what the OP is asking from the complexity classes that are mentioned. $\endgroup$ – Kaveh Sep 6 '13 at 7:20
  • $\begingroup$ Enumeration problems are not in #P (so not #P-complete) because the answer to any problem in #P is a non-negative integer. Most enumeration problems are not in any complexity class based on polynomial time bounds because of the potentially exponential number of solutions. $\endgroup$ – David Richerby Sep 6 '13 at 8:46
  • 1
    $\begingroup$ To me, the question is still unclear. You'd need a careful definition of "compression." For example, in triangle enumeration, if you permit "compression," then you could just output the input graph itself as a compressed representation of all triangles (since it loses no information of the input). $\endgroup$ – Yoshio Okamoto Sep 7 '13 at 15:54

Your Answer

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

Browse other questions tagged or ask your own question.