5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 ... $\endgroup$ – Dave Clarke Mar 31 '11 at 15:46
  • $\begingroup$ MikleB: I'm not sure if I understand your question correctly. Does the comment by Dave answer your question? $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 31 '11 at 16:07
  • 2
    $\begingroup$ @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. $\endgroup$ – Yoshio Okamoto Mar 31 '11 at 16:09
  • $\begingroup$ Ah. I didn't recognize the phrase "output polynomial time" as meaning "polynomical time wrt the output size". $\endgroup$ – Dave Clarke Mar 31 '11 at 16:12
  • $\begingroup$ Yes, polynomial in size of output and input. $\endgroup$ – MikleB Mar 31 '11 at 21:46
4
$\begingroup$

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

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