4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Please fix the title? $\endgroup$
    – Mohammad Al-Turkistany
    Aug 5, 2015 at 13:13
  • $\begingroup$ Oops, fixed. Thanks @MohammadAl-Turkistany $\endgroup$
    – Ian Gent
    Aug 5, 2015 at 13:15
  • $\begingroup$ If the reduction's target can have a portion designated as "this encodes the input instance and is not part of the original output" and there is an efficiently-computable counting translation function for the conversion from original output to modified output, then your reduction can be modified to remove the counting translation function's dependency on the input instance. $\hspace{.47 in}$ $\endgroup$
    – user6973
    Aug 5, 2015 at 16:01
  • $\begingroup$ 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). $\endgroup$
    – Ian Gent
    Aug 6, 2015 at 9:48
  • $\begingroup$ Oh, I forgot that one could easily hope for the counting translation function to also not depend on the output instance. $\:$ (My idea would not achieve that.) $\:$ What you just mentioned does seem like a good way to try to remove that dependency. $\:$ For that example, making X odd would be enough. $\;\;\;\;$ $\endgroup$
    – user6973
    Aug 6, 2015 at 10:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.