3
$\begingroup$

I want to know if there is counting reduction (weakly or strongly parsimonious) maintaining the length of the witness between two variations of $\#Knapsack$ problem. Let me define the problems first in decision version.

$Knapsack_{1} :$ $S_1$ is a set of $n_1$ items as follows $S_1 = \{a_1, a_2, \ldots,a_{n_1}\}$. $f : a_i\to \mathbb{N}$ is a function mapping each variable to some natural number. Two other integers $k$ $\leq$ $n_1$ and $B$ are given. $Question:$ Is there a subset $S^{'} \subseteq S_1$, $|S^'|= k$ such that $\Sigma_{z \in S^'}$ $f(z)$ $\leq$ $B$ $?$

Here the witness length is the number of bits required to represent $S^'$.

$Knapsack_{2} :$ $S_2$ is a set of $n_2$ items as follows $S_2 = \{b_1, b_2, \ldots,b_{n_2}\}$. $f : b_i\to \mathbb{N}$ is a function mapping each variable to some natural number. Another integer $C$ is given. $Question:$ Is there a binary string $x$ of length $n_2$ $( x = x_1x_2\ldots x_{n_2}$, $x_i \in \{0,1\} )$ such that $\Sigma_{i=1}^{n_2}$ $f(b_i)x_i$ $\leq$ $C$ $?$

Here the witness length is the number of bits required to represent $x$.

The way problems are defined, both the decision versions are actually solvable in polynomial time. But I am interested in counting version (i.e. the number of witnesses) and I think counting versions are $\#P$-complete. If we consider the length of the witness, for $Knapsack_1$ problem, it is $k.log(n_1)$. For $Knapsack_2$ length of the witness is $n_2$.

Now my question is, is it possible to find a counting reduction (weakly or strongly parsimonious) from $\#Knapsack_1$ to $\#Knapsack_2$ so that the length of the witness of the reduced problem instance is at most polynomially bounded to the length of the witness of the original problem instance $?$ I think in the opposite direction it is easy, just by taking $S_1 = S_2$. But for $\#Knapsack_1$ to $\#Knapsack_2$, it won't work as $n_2$ may not be polynomially bounded to $k.log(n_1)$ for any arbitrary $k$ if $n_1 = n_2$. Or can we show that it is not possible to find any such reduction unless some complexity theoretic assumption fails ? Any thoughts/references ?

$\endgroup$
  • $\begingroup$ No suggestion in this question yet ??? Disappointed.. :( $\endgroup$ – David Sep 30 '12 at 16:16

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.