<p><em>Quick version</em>: is there a definitive definition of weakly parsimonious counting reduction for #P?</p>

<p><em>Longer version:</em> I am doing a gadget based reduction for NPC and would like to use it for #P. The reduction definitely isn't strongly parsimonious and to keep it simpler I'd like to avoid making it so.  </p>

<p>Given the number of solutions to the reduced class, I can get a function which gives me the number of solutions to the original, <strong>IF</strong> I am allowed to put the original instance into the counting translation function. The number of solutions to the original is going to be something like the number of solutions to the translated problem divided by 2^n, where n is the number of variables in the original SAT problem. </p>

<p>Some definitions I've found on the web allow this and some don't, so I want to know if there is an important difference.</p>

CC BY-SA 3.0
2015-08-05T13:13:18.827Z
Please fix the title?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-05T13:15:31.150Z
Oops, fixed. Thanks @MohammadAl-Turkistany
Ian Gent
CC BY-SA 3.0
2015-08-06T09:48:32.287Z
Thanks @RickyDemer. Let me see if I got your point... so say it was as simple as the number of solutions is divided by 2^n. I can easily encode n somehow to make a new output and put this in a modified version of the translated problem. And I suppose I can then even make the number of solutions encode n itself, e.g. if the original number of solutions is X then instead of 2^n.X solutions I make it 2^n.X + n or something so n can be recovered from this number (not sure that would work but something would).
Ian Gent
<counting-complexity>
Can weakly parsimonious counting reductions use the input instance to compute the count?
Ian Gent
# Can weakly parsimonious counting reductions use the input instance to compute the count?

(Asked by: username_0 on 2015-08-05)

*Quick version*: is there a definitive definition of weakly parsimonious counting reduction for #P?

*Longer version:* I am doing a gadget based reduction for NPC and would like to use it for #P. The reduction definitely isn't strongly parsimonious and to keep it simpler I'd like to avoid making it so.

Given the number of solutions to the reduced class, I can get a function which gives me the number of solutions to the original, **IF** I am allowed to put the original instance into the counting translation function. The number of solutions to the original is going to be something like the number of solutions to the translated problem divided by 2^n, where n is the number of variables in the original SAT problem.

Some definitions I've found on the web allow this and some don't, so I want to know if there is an important difference.

**Tags:** counting-complexity

> **Comments:**
> **username_1**: Please fix the title?  
> **username_0**: Oops, fixed. Thanks @MohammadAl-Turkistany  
> **username_0**: Thanks @RickyDemer. Let me see if I got your point... so say it was as simple as the number of solutions is divided by 2^n. I can easily encode n somehow to make a new output and put this in a modified version of the translated problem. And I suppose I can then even make the number of solutions encode n itself, e.g. if the original number of solutions is X then instead of 2^n.X solutions I make it 2^n.X + n or something so n can be recovered from this number (not sure that would work but something would).  

---

## 0 answers

