# Subset $k$-product

Subset $k$-sum problem has been well studied as a fixed parameter version of subset sum.

What is known about the analogous Subset $k$-product problem which is the fixed parameter version of subset product?

I am interested in the case where the base field has characteristic $0$ and not $0$ and large of order $O(2^n)$ where $n$ is the number of elements as input to the problem.

Is there a faster than $n^{O(k)}$ algorithm for this problem?

• $O(n^k)$ brute-force searches size-$k$ subsets. Modify this by: 1. At the beginnning, sort the list of numbers. 2. Brute-force search over size-$k-1$ subsets. 3. Let $z$ be the target product. For each distinct set of $k-1$ multiplicands $a_1, ..., a_{k-1}$, we need to know whether $y\stackrel{\rm def}{=} z/\prod_i a_i, y\ne a_i\forall i$ is in the list, so perform binary search for $y$. Running time: $O(n\log n) + O(n^{k-1}\log n) < O(n^k)$ – Daniel Apon Nov 25 '13 at 13:54
• This is still $n^{O(k)}$. Sorry about the typo before. – 1.. Nov 26 '13 at 7:19

Over the integers, it looks like Subset Product is at least as hard as the Exact Cover problem

http://en.wikipedia.org/wiki/Exact_cover

parametrized by the number of sets used in the exact cover. (For the reduction, one assigns a distinct prime to each element of the ground set.)

I couldn't find a reference, but I'm guessing that this problem is $W[1]$-hard and so unlikely to have an $f(k) \cdot n^{O(1)}$-time algorithm. (I would look in Downey-Fellows or other textbooks on FPT theory.) Maybe one could rule out $n^{o(k)}$ running time under the Exponential Time Hypothesis or Strong ETH. The paper of Patrascu-Williams might be a starting point.

Sorry for not knowing much, but I figured this is better than nothing.

• I am aware of Patrascu-Williams paper. I think this problem is easier than $k$-subset sum for the fixed parameter case. – 1.. Nov 27 '13 at 8:54
• Do you think the following case is also similar to $W[1]$ hard? Let the $n$ given integers be partitioned to $k\sim\log_2(n)$ classes of size $\lfloor\frac{n}{k}\rfloor\pm 1$. One needs to find if there is a combination of $k$ terms (with one term per class) such that the $k$-terms multiply to a given number over field of char $0$ or $p\sim O(2^n)$? Here $k$ is not fixed but small enough and each of the classes have different terms. – 1.. Nov 27 '13 at 9:09
• Hmm, I don't know, sorry... – Andy Drucker Dec 4 '13 at 19:27

Any efficient algorithm to solve the subset $k$-product problem (for $k$ large enough) would also give an efficient algorithm to solve the discrete logarithm problem in that field. Therefore, if you are working in a large finite field where the discrete log is hard (e.g., $GF(p)$ where $p$ is a sufficiently large prime), there is no hope for an efficient algorithm to solve the subset $k$-product problem.

Conversely, if you are working in a field where the discrete logarithm problem is easy, it is easy to convert any instance of the subset $k$-product problem to the subset $k$-sum problem: just take discrete logs. Therefore, if the discrete log problem is easy, subset $k$-product is no harder than subset $k$-sum.

• @J.A, a formal proof of what? (I didn't say subset product is easier than subset sum, so don't use me as your source for that. Personally, I would be surprised if that were the case.) – D.W. Dec 2 '13 at 8:02
• Well this is what I was thinking. If DLog is easy then subset product is easy. That is why I was stating that. However I just nticed you stated the olpposikte (if subset product is easy then dlog is easy) – 1.. Dec 2 '13 at 8:04
• @J.A, but that doesn't follow. If DLog is easy, it doesn't necessarily follow that subset product is easy. I think the proper conclusion is: If DLog is easy, then subset $k$-sum and subset $k$-product are about the same level of hardness (either both easy, or both hard). – D.W. Dec 2 '13 at 8:05