2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ $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)$ $\endgroup$ – Daniel Apon Nov 25 '13 at 13:54
  • $\begingroup$ This is still $n^{O(k)}$. Sorry about the typo before. $\endgroup$ – T.... Nov 26 '13 at 7:19
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am aware of Patrascu-Williams paper. I think this problem is easier than $k$-subset sum for the fixed parameter case. $\endgroup$ – T.... Nov 27 '13 at 8:54
  • $\begingroup$ 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. $\endgroup$ – T.... Nov 27 '13 at 9:09
  • $\begingroup$ Hmm, I don't know, sorry... $\endgroup$ – Andy Drucker Dec 4 '13 at 19:27
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @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.) $\endgroup$ – D.W. Dec 2 '13 at 8:02
  • $\begingroup$ 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) $\endgroup$ – T.... Dec 2 '13 at 8:04
  • $\begingroup$ @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). $\endgroup$ – D.W. Dec 2 '13 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.