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.

$\endgroup$
  • $\begingroup$ Please fix the title? $\endgroup$ – Mohammad Al-Turkistany Aug 5 '15 at 13:13
  • $\begingroup$ Oops, fixed. Thanks @MohammadAl-Turkistany $\endgroup$ – Ian Gent Aug 5 '15 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 '15 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 '15 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 '15 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.