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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Peter Hofschatter Mar 22 at 17:17
  • $\begingroup$ Are you getting the direction of the reduction wrong? $\endgroup$ – Yuval Filmus Mar 22 at 17:35
  • $\begingroup$ $PARTITION \leq MOD-PARTITION$ $\endgroup$ – Peter Hofschatter Mar 22 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$ – Yuval Filmus Mar 22 at 17:55

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.