1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Totality, I completely rewrote your question. Please check that I didn't introduce any errors and that I am still asking the same question. $\endgroup$ – Tyson Williams Mar 12 '13 at 12:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Mar 12 '13 at 16:35
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What happens if the total number of witnesses is exponential, but we only wishes to find polynomially many of them? $\endgroup$ – Totality Mar 12 '13 at 13:02
  • 2
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Mar 12 '13 at 13:24

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.