2
$\begingroup$

MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \mod k \; = \; (\sum_{a \in A \setminus X} w(a) * a) \mod k$?

Can some please provide some idea on how to prove the NP-Completeness of this problem? I saw the proof of the set-partition problem (using a reduction from subset-sum) and I suppose, that this proof maybe will be some little modification of it.

$\endgroup$

1 Answer 1

2
$\begingroup$

Showing that this your problem is in NP is easy.

To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.

$\endgroup$
4
  • $\begingroup$ You cannot choose a modulus $k$, because it is given by mod-partition problem instance. You want to find two sets, which sum modulo by $k$ will be equal. $\endgroup$ Commented Mar 22, 2020 at 17:17
  • $\begingroup$ Are you getting the direction of the reduction wrong? $\endgroup$ Commented Mar 22, 2020 at 17:35
  • $\begingroup$ $PARTITION \leq MOD-PARTITION$ $\endgroup$ Commented Mar 22, 2020 at 17:42
  • 1
    $\begingroup$ Right. So given an instance of PARTITION, you need to construct an equivalent instance of MOD-PARTITION. You get to choose $k$. $\endgroup$ Commented Mar 22, 2020 at 17:55

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.