<p>I don't know any reference, so just an extended comment:</p>

<p>If you allow a <em>succinct</em> representation for the input integers, i.e. you can represent the input integers as factors, then the "multiplicative" versions of Knapsack are NP-complete; indeed: </p>

<p>$\sum_{i=1}^n w_i x_i \leq W$ can be reduced to the equivalent $\prod_{i=1}^n 2^{w_i} x_i \leq 2^W$;</p>

<p>and $\sum_{i=1}^n v_i x_i$ maximization can be reduced to  $\prod_{i=1}^n 2^{v_i} x_i$ maximization.</p>

<p>I didn't think about it too much but the above reduction should work even if we require that in a mixed instance ( maximize sum of values under multiplicative weight constraint OR maximize product of values under addictive weight constraint ) all input values must be given with their prime factorization (building a direct reduction from exact cover).</p>

<p>Without a succinct representation the above reduction doesn't work because Knapsack is not strongly NPC.</p>

CC BY-SA 3.0
2015-07-08T12:30:03.103Z
So suppose I consider sub-problem where elements to make the product must be represented as factors (e.g. powers of two). Then, the reduction should be polynomial. If this sub-problem is already NP-hard, it should implie that the general problem is hard, isn't it?
Olf
CC BY-SA 3.0
2015-04-21T16:21:56.823Z
2015-04-21T16:21:56.823Z
Marzio De Biasi
<p>I cannot find references concerning the complexity of the variant of the knapsack problem (decision version) where one of the two conditions must be a product instead of a sum (0 not allowed). </p>

<p>A related question is this one: <a href="https://cstheory.stackexchange.com/questions/20559/combining-subset-sum-and-subset-product-problems">Combining subset sum and subset product problems</a> .</p>

<p>It is well known that we can say that knapsack is the special case of subset sum (where each weight is equal to each profit and the bounds are the same) to satisfy the equality of subset sum with 2 inequalities. However, this is not possible here since there are 2 equalities to satisfy in the "subset sum product" problem and we have only 2 inequalities in the "knapsack sum product". </p>

<cc.complexity-theory><reference-request>
Knapsack combining sum and product
Olf
# Knapsack combining sum and product

(Asked by: username_0 on 2015-04-21)

I cannot find references concerning the complexity of the variant of the knapsack problem (decision version) where one of the two conditions must be a product instead of a sum (0 not allowed).

A related question is this one: [Combining subset sum and subset product problems](https://cstheory.stackexchange.com/questions/20559/combining-subset-sum-and-subset-product-problems) .

It is well known that we can say that knapsack is the special case of subset sum (where each weight is equal to each profit and the bounds are the same) to satisfy the equality of subset sum with 2 inequalities. However, this is not possible here since there are 2 equalities to satisfy in the "subset sum product" problem and we have only 2 inequalities in the "knapsack sum product".

**Tags:** cc.complexity-theory, reference-request

---

## 1 answers

### Answer by username_1 on 2015-04-21. Score: 1

I don't know any reference, so just an extended comment:

If you allow a *succinct* representation for the input integers, i.e. you can represent the input integers as factors, then the "multiplicative" versions of Knapsack are NP-complete; indeed:

$\sum\_{i=1}^n w\_i x\_i \leq W$ can be reduced to the equivalent $\prod\_{i=1}^n 2^{w\_i} x\_i \leq 2^W$;

and $\sum\_{i=1}^n v\_i x\_i$ maximization can be reduced to $\prod\_{i=1}^n 2^{v\_i} x\_i$ maximization.

I didn't think about it too much but the above reduction should work even if we require that in a mixed instance ( maximize sum of values under multiplicative weight constraint OR maximize product of values under addictive weight constraint ) all input values must be given with their prime factorization (building a direct reduction from exact cover).

Without a succinct representation the above reduction doesn't work because Knapsack is not strongly NPC.

> **Comments:**
> **username_0**: So suppose I consider sub-problem where elements to make the product must be represented as factors (e.g. powers of two). Then, the reduction should be polynomial. If this sub-problem is already NP-hard, it should implie that the general problem is hard, isn't it?  

---

