# Is the "modular subset product" problem NP-complete?

While examining some $NP$-complete problems relating to sets of integers, a question flashed through my mind: whether the $NP$-completeness of these problems is retained when integer arithmetic is replaced by modular arithmetic?

A concrete example is the subset product problem, which was known to be $NP$-complete. I wonder if we consider the problem over ring $\mathbb{Z}_n$, as formulated below, it is still $NP$-complete?

Given $t, n \in \mathbb{N}$ and a finite set of integers $S$, determine whether there exists $S' \subseteq S$ such that $\prod_{s \in S'}s \equiv t \pmod n$.

My principal difficulty in approaching the problem is that I cannot figure out how the (polynomial) reduction works, supposing the $NP$-completeness is retained, due to the "cyclic" behavior of modular arithmetic. I've tried to search for variants of the problem but no luck. Thank you for any explanations, suggestions or references.

• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions.
– Raphael
Apr 28 '16 at 11:49

The claim that you linked to (that subset product is strongly $NP$-complete), is incorrect: it is only weakly so. The numbers $s\in S$ are small and can be represented in unary, but $t$ has to be represented in binary for the reduction to work.

If you consider it over $\mathbb{Z}_n$ it remains weakly $NP$-complete, since we can just take $n$ to be $\Pi_{s\in S} s$. In this case, the fact that we're doing modular arithmetic becomes irrelevant. $n$ will be exponential in $\Sigma_{s\in S} s$ so that $\log n$ (the size of a binary representation of $n$) will be polynomial in the size of the original instance (in which all $s\in S$ were represented in unary).

• Thank you for your answer but I have encountered a difficulty in understanding the connection between the original and the modular version and how the reduction works: What is the purpose of the elimination of modular arithmetic? If $n$ is much less than $\Pi_{s \in S} s$, the $NP$-completeness of the problem is still retained? What is the purpose of representing all $s \in S$ in unary? Would you please give me a more detailed explanation with examples, or provide me references that could help me gain a complete understanding on this problem? Thank you. Apr 30 '16 at 16:47