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

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

<ol>
<li>There are at least $2^{\binom{n}{2}}/2$ Hamiltonian graphs.</li>
<li>There are at least $2^{\binom{n}{2}}/2$ non-Hamiltonian graphs.</li>
</ol>

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

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

CC BY-SA 2.5
2011-04-01T12:47:54.327Z
2011-04-01T12:47:54.327Z
Yoshio Okamoto
<p>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?</p>

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

CC BY-SA 2.5
2011-03-31T15:46:26.510Z
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
CC BY-SA 2.5
2011-03-31T16:07:31.077Z
MikleB: I'm not sure if I understand your question correctly. Does the comment by Dave answer your question?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-31T16:09:20.717Z
@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
CC BY-SA 2.5
2011-03-31T16:12:16.940Z
Ah. I didn't recognize the phrase "output polynomial time" as meaning "polynomical time wrt the output size".
Dave Clarke
CC BY-SA 2.5
2011-03-31T21:46:59.183Z
Yes, polynomial in size of output and input.
MikleB
<cc.complexity-theory><np-hardness>
Enumeration of discrete objects for which recognition problem is coNP-complete
MikleB
# Enumeration of discrete objects for which recognition problem is coNP-complete

(Asked by: username_0 on 2011-03-31)

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.

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: 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 ...  
> **username_2**: username_0: I'm not sure if I understand your question correctly. Does the comment by Dave answer your question?  
> **username_3**: @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.  
> **username_1**: Ah. I didn't recognize the phrase "output polynomial time" as meaning "polynomical time wrt the output size".  
> **username_0**: Yes, polynomial in size of output and input.  

---

## 1 answers

### Answer by username_3 on 2011-04-01. Score: 4

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}}$.


---

