# Is this special case of the subset-product problem $\mathsf{NP}$-complete?

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.

• 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. Jun 11, 2022 at 8:43

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