2

It seems that most NP-complete decision problems have #P-complete corresponding counting problems, with many examples showing this and no known counterexamples. In Jerrums' lecture notes `Counting, Sampling and Integrating: Algorithms and Complexity' he writes that "the existing reductions used to establish NP-completeness of decision problems $\Pi$ are often parsimonious and hence establish also #P-completeness of the corresponding counting problem $\#\Pi$. When the existing reduction is not parsimonious it can be modified so that it becomes so."

In general I would like for this quote to be explained a bit further, but more specifically how exactly do we make this leap from the reduction of a decision problem to reductions of its corresponding counting problem? Is there a general method for doing so, or a vague outline? Also if possible, an example or reference to an example of this method would be great.

a3nm
  • 9,269
  • 27
  • 86
space_kale
  • 21
  • 1
  • 2
    The contention here is that for typical reductions between typical NP-complete problems, the reduction already is a reduction of the corresponding counting problems as well, as it preserves the number of witnesses, not just their existence. In case it isn't, it has to be modified in an ad hoc way (if possible at all); there is no general recipe. – Emil Jeřábek Dec 07 '23 at 06:55
  • 2
    higly related: https://cstheory.stackexchange.com/questions/16119/when-does-x-is-np-complete-imply-x-is-p-complete?rq=1 – holf Dec 07 '23 at 07:39

0 Answers0