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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.