Knapsack combining sum and product

Question

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 .

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".

Answer 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.