<p><em>Thanks for the comments, I refined the question.</em></p>

<p>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.</p>

<p>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?</p>

<p>More specifically, </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>Could anyone give any explanations or references? </p>

CC BY-SA 3.0
2013-09-06T01:33:56.883Z
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.
Yury
CC BY-SA 3.0
2013-09-06T06:55:04.427Z
@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.
David Richerby
CC BY-SA 3.0
2013-09-06T07:20:14.013Z
@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.
Kaveh
CC BY-SA 3.0
2013-09-06T08:46:57.757Z
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.
David Richerby
CC BY-SA 3.0
2013-09-07T15:54:41.657Z
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).
Yoshio Okamoto
<cc.complexity-theory>
What is the complexity relationship between counting and enumeration problems?
xiaom
# What is the complexity relationship between counting and enumeration problems?

(Asked by: username_0 on 2013-09-06)

*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?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  
> **username_3**: @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.  
> **username_2**: 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.  
> **username_4**: 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).  

---

## 0 answers

