3
$\begingroup$

The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more restrictive type: polytime one-one reductions do indeed preserve the number of solutions.

Suppose $f:\Sigma^{\ast}\to \mathbb{N}$ is a counting function in $\text{#P}$ and the decision problem $f_{ > 0}$ defined as: Is $f(x) > 0$ ? is in $NP$.

Now if $f_{> 0}$ is in $\text{NP-Complete}$, can we immediately tell that $f$ is in $\text{#P-Complete}$ or, do we could only say so, if the reduction map (showing $\text{NP-Completeness}$) was one-one.

$\endgroup$
  • 2
    $\begingroup$ Up to my (poor :-) knowledge it is an open problem, i.e. an example of a polytime many-one reduction that cannot be made parsimonious (polytime one-one) has not been found yet. I think that further details can be found in J. Simon. On the difference between one and many $\endgroup$ – Vor Aug 23 '12 at 9:54
  • 1
    $\begingroup$ ps: we know that the reverse direction does not hold (unless strange things happens in complete theory, i.e. P=NP) since the counting version of Matching is #P-complete while the search version can be solved in polytime so decision version is in P. $\endgroup$ – Kaveh Aug 23 '12 at 12:19
  • 2
    $\begingroup$ @Kaveh: you are right, even "parsimonious reduction" (I used my comment above) is not correct. #P-hardness is defined using weakly parsimonious reductions (counting reductions). From Algebraic Techniques for Satisfiability Problems: "... In the constraint context, there are satisfiability problems, where the problem if a given formula has a solution at all is NP-complete, but the corresponding counting problem is not complete for #P under parsimonious reductions. ..." $\endgroup$ – Vor Aug 23 '12 at 13:57
  • 1
    $\begingroup$ @Vor, actually I am not sure that is the standard definition of #P-hardness, e.g. see Arora and Barak, definition 17.8, or #P-complete on Wikipedia. The definition in Valiant's paper is as follows: $A$ is #P-hard iff $\mathsf{FP}^A$ contains #P. The definition doesn't talk about preserving the number of solutions, however the proof of #P-completeness of #3SAT satisfies the condition. $\endgroup$ – Kaveh Aug 23 '12 at 15:36
  • 1
    $\begingroup$ @Kaveh: I was only trying to express that the definition of #P-hardness under counting reductions (which I found in some papers) seems stronger than the Valiant's definition of #P-hardness. $\endgroup$ – Vor Aug 23 '12 at 23:21

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.