# How to prove the NP-completeness of MOD-PARTITION

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.

## 1 Answer

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.

• 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. – Peter Hofschatter Mar 22 '20 at 17:17
• Are you getting the direction of the reduction wrong? – Yuval Filmus Mar 22 '20 at 17:35
• $PARTITION \leq MOD-PARTITION$ – Peter Hofschatter Mar 22 '20 at 17:42
• Right. So given an instance of PARTITION, you need to construct an equivalent instance of MOD-PARTITION. You get to choose $k$. – Yuval Filmus Mar 22 '20 at 17:55