# Enumeration of discrete objects for which recognition problem is coNP-complete

Is there any problem of enumeration of discrete objects for which problem of recognizing of these discrete objects is coNP-complete (or NP-complete), but it is possible to enumerate all these objects in output polynomial time?

For example (but I don't know about the complexity of enumeration) the problem of enumeration (generation) all Hamiltonian graphs with no more than n vertices.

• If you can enumerate all the objects (up to a certain size) in polynomial time, then you can use this as the basis of a polynomial-time algorithm for recognising the discrete objects. From which you can conclude ... – Dave Clarke Mar 31 '11 at 15:46
• MikleB: I'm not sure if I understand your question correctly. Does the comment by Dave answer your question? – Hsien-Chih Chang 張顯之 Mar 31 '11 at 16:07
• @Dave: If you can enumerate all the objects in polynomial time w.r.t. the input size, then you're right. But here the question is about polynomial time w.r.t. the output size. – Yoshio Okamoto Mar 31 '11 at 16:09
• Ah. I didn't recognize the phrase "output polynomial time" as meaning "polynomical time wrt the output size". – Dave Clarke Mar 31 '11 at 16:12
• Yes, polynomial in size of output and input. – MikleB Mar 31 '11 at 21:46

This is not a complete answer, but let me try to explain the case for the Hamiltonian graphs and the non-Hamiltonian graphs with $n$ vertices.
There are $2^{\binom{n}{2}}$ graphs on $n$ vertices, and each of them is either Hamiltonian or non-Hamiltonian. So one of the following is true.
1. There are at least $2^{\binom{n}{2}}/2$ Hamiltonian graphs.
2. There are at least $2^{\binom{n}{2}}/2$ non-Hamiltonian graphs.
I don't know which is true, but suppose 1 is true. Let $H(n)$ be the number of Hamiltonian graphs with $n$ vertices. Then $H(n)\geq 2^{\binom{n}{2}}/2$. In this case, listing all the Hamiltonian graphs with $n$ vertices can be easily done in output polynomial time: Look through all the $2^{\binom{n}{2}}$ graphs, check the Hamiltonicity for each of them (in $2^{O(n)}$ time), and output if it is Hamiltonian. The running time is $O(2^{\binom{n}{2}}\times 2^{O(n)}) = O(H(n)^2)$, since $2^{O(n)} = O(H(n))$. If 2 is true, then by the same argument we can list all the non-Hamiltonian graphs with $n$ vertices in output polynomial time.
Namely, if the output size is polynomial in $2^{\binom{n}{2}}$, then such a trivial algorithm runs in output polynomial time (assuming that the verification can be done in $\text{poly}(2^{\binom{n}{2}})$ time). So the only interesting cases are when the output sizes are subpolynomial in $2^{\binom{n}{2}}$.