2
$\begingroup$

It is a well known fact that the following 'subset-product' problem is $\mathsf{NP}$-complete when $n/\log M \in \Theta(1)$.

Consider a size-$n$ subset of a multiplicative group $\mathbb{G}\cong\mathbb{Z}^{*}_M$. Then an instance of the subset-product problem consists of $(a_1, a_2,\dots,a_n, t)$ with each $a_i, t\in \mathbb{G}$ and the problem asks to find a (possibly $s(n)$-size, where $s(n)\in\Theta(n)$) subset $S\subset[n]$ such that $\prod_{i\in S}a_i = t$.

Is the special case where $t=1$ also $\mathsf{NP}$-complete? In particular, can every instance of the subset-product problem be reduced to an instance where one needs to find a subset whose product is $1_{\mathbb{G}}$?

Since the fact is true for the related subset-sum problem (that every general subset-sum instance can be reduced to one in which the goal is to find a subset which sums to $0$) it could possibly be true. Are there any known results which deal with the above? References would be appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ SUBSET SUM is NP-complete even when the target is $0$. If $M$ is a large prime and we know a primitive root modulo $M$, or at least an element with large order, then we can reduce SUBSET SUM to your problem with the given $M$, assuming $M$ is large enough (larger than the sum of absolute values of the input subset). This shows that your problem is NP-hard with respect to randomized reductions. $\endgroup$ Commented Jun 11, 2022 at 8:43

1 Answer 1

3
$\begingroup$

Yes, your problem is NP-complete, even when we restrict to the case where $t=1$.

We will focus on the case $M=2^k$. Then $\mathbb{Z}_M^*$ is isomorphic to $\mathbb{Z}_2 \times \mathbb{Z}^{2^{k-2}}$, and $3$ has order $2^{k-2}$ in $\mathbb{Z}_M^*$, so the subgroup generated by $3$ modulo $M$ is isomorphic to $\mathbb{Z}^{2^{k-2}}$. (See https://math.stackexchange.com/q/2460124/14578.)

This lets us reduce the ordinary subset sum problem to your problem. Suppose we have an instance of (positive) subset sum, namely, $x_1,\dots,x_n \ge 0$ and a target $y$; the question is whether there exists a subset of the $x_i$'s that sum to $y$. Choose $k$ large enough that $2^{k-2} \ge x_1 + \dots + x_n$, and set $M=2^k$. Let $a_i = 3^{x_i} \bmod M$, $a_{n+1} = 3^{-y} \bmod M$, and $t=1$. Then there is a solution to your problem (with values $a_1,\dots,a_{n+1}$ and target $t=1$) iff there is a solution to the original subset sum instance. This shows how to reduce the (positive) subset sum problem to your problem with $t=1$, which proves that your problem is NP-complete.

My thanks to Yuval Filmus for the main ideas underlying this answer.


This doesn't prove that your problem is hard for all $M$. There may well be choices of $M$ where the problem is easy. In particular, for the special case where $M=3 \times 5 \times 7 \times 11 \times \cdots \times p$ is the product of the first few primes, I'm not sure whether the problem remains NP-complete or not. (Why do I have some doubts? Well, the subset sum problem is not hard over $\mathbb{Z}_2^k$: it can be solved in polynomial time with linear algebra. When $M=3 \times \cdots \times p$, then $\mathbb{Z}_M^*$ is isomorphic to $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_4 \times \mathbb{Z}_6 \times \cdots \mathbb{Z}_{p-1}$, and the isomorphism can be efficiently computed in both directions using the Chinese remainder theorem. So when $M$ has this special form, the situation feels somehow close to the case of $\mathbb{Z}_2^k$, and I'm not sure whether there might some sophisticated generalization of linear algebra that can be used to solve the subset sum problem over $\mathbb{Z}_M^*$ efficiently or not.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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