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

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

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.

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