14
$\begingroup$

1) Is it possible to have a parsimonious reduction from a #P-complete problem #A to a counting problem #B when (the decision version) A is NP-complete and the B is in P?

For example, can there be a parsimonious reduction from #SAT to #B, when B is in P?

2) If B is in P, what are the different possibilities for the complexity of #B?

$\endgroup$
20
$\begingroup$

If you insist on parsimonious reductions (where the number of solutions is preserved) you cannot have such a reduction unless P = NP because the decision algorithm for non-emptyness of solutions for B will give you a decision algorithm for non-emptyness of solutions for A. On the other hand, if you allow other kind of reductions you can have such a case. For example, Valiant showed that #SAT reduces to the problem of counting perfect matchings in a bipartite graph: the reduction starts with a CNF-formula $F$ and builds a bipartite graph $G$ whose number of perfect matchings mod $2^{8m}+1$ is $4^m$ times the number of satisfying assignments of $F$, where $m$ is the number of literal occurrences in $F$. Note how this is not a parsimonious reduction, but a reduction nonetheless since you can recover the number of satisfying assignments of $F$ from the number of perfect matchings of $G$.

See Chapter 18 in Papadimitriou's "Computational Complexity" book for a clear exposition of this.

$\endgroup$
7
$\begingroup$

The answer to the question 2 is that the complexity of the counting problem #B can be basically anything (not even necessarily computable). More precisely, the restriction that the decision version is in P does not have any implication on the complexity of the counting version. This is because you can add a dummy solution to any relation problem so that the decision version becomes trivial (the answer becomes always yes) without changing the complexity of the counting version.

$\endgroup$
  • 1
    $\begingroup$ why do u say so?"(not even necessarily computable)" It is clear that if B is a decision problem in P then the #B is in #P, directly from the definition of class #P! but proving #B is also #P-com is important, and adding dummy solutions should not effect on the complexity of counting. you agree? $\endgroup$ – marjoonjan Dec 1 '10 at 19:16
  • $\begingroup$ @marjoonjan: “It is clear that if B is a decision problem in P then the #B is in #P, directly from the definition of class #P” That is false. Also, I get the impression that you believe that a decision problem B uniquely determines the counting problem #B, but it is not the case, as I explained in this answer. $\endgroup$ – Tsuyoshi Ito Dec 1 '10 at 19:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.