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

<p><a href="http://en.wikipedia.org/wiki/Exact_cover">http://en.wikipedia.org/wiki/Exact_cover</a></p>

<p>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.)</p>

<p>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.</p>

<p>Sorry for not knowing much, but I figured this is better than nothing.</p>

CC BY-SA 3.0
2013-11-27T08:54:27.227Z
I am aware of Patrascu-Williams paper. I think this problem is easier than $k$-subset sum for the fixed parameter case.
Turbo
CC BY-SA 3.0
2013-11-27T09:09:46.573Z
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.
Turbo
CC BY-SA 3.0
2013-12-04T19:27:40.497Z
Hmm, I don't know, sorry...
Andy Drucker
CC BY-SA 3.0
2013-11-27T00:49:46.677Z
2013-11-27T00:49:46.677Z
Andy Drucker
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-12-02T08:02:47.860Z
@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.
CC BY-SA 3.0
2013-12-02T08:04:08.500Z
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)
Turbo
CC BY-SA 3.0
2013-12-02T08:05:39.620Z
@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.
CC BY-SA 3.0
2013-12-02T00:46:18.303Z
2013-12-02T00:46:18.303Z
D.W.
<p>Subset $k$-sum problem has been well studied as a fixed parameter version of subset sum.</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2013-11-25T13:54:55.930Z
$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
CC BY-SA 3.0
2013-11-26T07:19:46.377Z
This is still $n^{O(k)}$. Sorry about the typo before.
Turbo
<cc.complexity-theory><ds.algorithms>
Subset $k$-product
Turbo
# Subset $k$-product

(Asked by: username_0 on 2013-11-24)

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?

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: $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)$  
> **username_0**: This is still $n^{O(k)}$. Sorry about the typo before.  

---

## 2 answers

### Answer by username_2 on 2013-11-27. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: I am aware of Patrascu-Williams paper. I think this problem is easier than $k$-subset sum for the fixed parameter case.  
> **username_0**: 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.  
> **username_2**: Hmm, I don't know, sorry...  

---

### Answer by username_3 on 2013-12-02. Score: 1

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.

> **Comments:**
> **username_3**: @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.)  
> **username_0**: 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)  
> **username_3**: @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).  

---

