0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael ♦
    Apr 28, 2016 at 11:49

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Khoa Tran
    Apr 30, 2016 at 16:47
  • $\begingroup$ The link is dead. $\endgroup$
    – orlp
    Dec 30, 2020 at 0:12
0
$\begingroup$

Yes it is still NP because it can be modified or altered into satisfactory algorithm and the numbers which are mentioned s∈S are given as unary but 't' has to be given in binary. This will in turn reduce work load.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This doesn't answer the question; the question didn't ask whether the problem is in NP; it asked whether the problem is NP-complete. Apart from that, I can't tell what you are trying to say. Also I can't tell what this adds over the other, earlier answer (it seems to repeat material from there). Can you edit this answer to clarify what you're trying to say? $\endgroup$
    – D.W. ♦
    Apr 29, 2016 at 2:57

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.