$\begingroup$
$\endgroup$
18
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.
Dave Clarke
20.4k4 gold badges70 silver badges114 bronze badges
asked Aug 22, 2012 at 23:09
Pavithran Iyer
3852 silver badges7 bronze badges
-
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– Vor2012年08月23日 09:54:00 +00:00Commented Aug 23, 2012 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– Kaveh2012年08月23日 12:19:23 +00:00Commented Aug 23, 2012 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– Vor2012年08月23日 13:57:11 +00:00Commented Aug 23, 2012 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– Kaveh2012年08月23日 15:36:58 +00:00Commented Aug 23, 2012 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– Vor2012年08月23日 23:21:43 +00:00Commented Aug 23, 2012 at 23:21