<p>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 &quot;the existing reductions used to establish NP-completeness of decision problems <span class="math-container">$\Pi$</span>  are often parsimonious and hence establish also #P-completeness of the corresponding counting problem <span class="math-container">$\#\Pi$</span>. When the existing reduction is not parsimonious it can be modified so that it becomes so.&quot;</p>
<p>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.</p>

CC BY-SA 4.0
2023-12-07T06:55:31.513Z
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
CC BY-SA 4.0
2023-12-07T07:39:38.943Z
higly related: https://cstheory.stackexchange.com/questions/16119/when-does-x-is-np-complete-imply-x-is-p-complete?rq=1
holf
<cc.complexity-theory><counting-complexity>
Extending Karp Reductions of a Decision Problem to Cook Reductions of the Associated Counting Problem
space_broccoli
# Extending Karp Reductions of a Decision Problem to Cook Reductions of the Associated Counting Problem

(Asked by: username_0 on 2023-12-07)

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.

**Tags:** cc.complexity-theory, counting-complexity
> **Comments:**
> **username_1**: 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.  
> **username_2**: higly related: https://cstheory.stackexchange.com/questions/16119/when-does-x-is-np-complete-imply-x-is-p-complete?rq=1  

---

## 0 answers

