# Does polynomially bounded number of witnesses and polynomial time decidability imply polynomial time enumeration?

Let us assume that $\text{P=NP}$.

Let $\#\Pi$ be a counting problem in $\#\mathrm{P}$ and let $\Pi$, the decision version that asks if the count is positive, be in $\mathrm{P}$.

In general, instances to a problem in $\#\mathrm{P}$ may have a count that is exponentially larger than the input size. Suppose however that for any instance to $\#\Pi$, the count is bounded by some fixed polynomial of the input size.

Given these assumptions, can we enumerate all witnesses being counted by $\#\Pi$ in polynomial time when $\text{P=NP}$?

• Totality, I completely rewrote your question. Please check that I didn't introduce any errors and that I am still asking the same question. Mar 12 '13 at 12:16
• Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. Mar 12 '13 at 16:35

Yes, you can do this unconditionally in $\mathrm{FP^{NP}}$, which equals $\mathrm{FP}$ by your assumption.

The algorithm is a version of binary search: if the witnesses you want to count are binary strings of length $n^k$, then compute by iteration on $i\le n^k$ the list of all their prefixes of length $i$. This list has polynomial length during the computation since there are only polynomially many witnesses in total, and given a prefix of length $i$, we can check which of its extensions of length $i+1$ are prefixes of a witness by an $\mathrm{NP}$ query.

• What happens if the total number of witnesses is exponential, but we only wishes to find polynomially many of them? Mar 12 '13 at 13:02
• If you want $s$ witnesses, use the same algorithm as above, but after each iteration retain only $s$ prefixes and drop the rest (if there are more). Mar 12 '13 at 13:24