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

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

CC BY-SA 3.0
2013-03-12T13:02:33.257Z
What happens if the total number of witnesses is exponential, but we only wishes to find polynomially many of them?
Totality
CC BY-SA 3.0
2013-03-12T13:24:52.063Z
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).
Emil Jeřábek
CC BY-SA 3.0
2013-03-12T12:44:02.210Z
2013-03-12T12:44:02.210Z
Emil Jeřábek
<p>Let us assume that $\text{P=NP}$.</p>

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

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

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

CC BY-SA 3.0
2013-03-12T12:16:50.110Z
Totality, I completely rewrote your question.  Please check that I didn't introduce any errors and that I am still asking the same question.
Tyson Williams
CC BY-SA 3.0
2013-03-12T16:35:55.403Z
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 [cs.se] which has a broader scope.
Kaveh
<cc.complexity-theory>
Does polynomially bounded number of witnesses and polynomial time decidability imply polynomial time enumeration?
Totality
# Does polynomially bounded number of witnesses and polynomial time decidability imply polynomial time enumeration?

(Asked by: username_0 on 2013-03-12)

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

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: username_0, I completely rewrote your question.  Please check that I didn't introduce any errors and that I am still asking the same question.  
> **username_2**: 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 [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_3 on 2013-03-12. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: What happens if the total number of witnesses is exponential, but we only wishes to find polynomially many of them?  
> **username_3**: 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).  

---

