# How to prove this “np-complete” problem?

I have a problem that I need to prove its np-completness: My original question

I need to reduce it from some problem, i´m trying to do it from some other than knapsack, that´s why I ask again. I need two sets $A$ and $B$ of equal cardinality $|A|=|B|$ and $\sum{A}\leq V$ and $\sum{B}\leq V$.

• It is like Partition, but sums must not be the same, must be less or equal than a fixed $V$, and cardinality must be equal.
• It is also like Bin-Packing problem with $k = 2$ (numbers of bins), but need to guarantee equal cardinality.
• I tried also with Sub-Set-Sum, but need to guarantee that the elements sum at most $k$, not exactly $k$.

Note: The problem with knapsack is that knapsack can select any items in no particular order from the list of objetcs, and my problem need to select (if selects) the first $k$ objects if they fit in the two sets.

PS: If anything is unclear, please comment and I'll explain!

• This looks like it should be an edit to your previous question: this one can't be understood without reading that one. And why do you care whether or not the reduction is from knapsack? – David Richerby Jan 20 '17 at 16:45
• Your problem looks similar to Select a subset of the columns in 2×n matrix, is it easy? – Zir Jan 20 '17 at 16:57
• @DavidRicherby - It seems that it should, but I'm new to stackexchange site and didn't know whether I should have edited my previous question or create a new one. My mistake!. Also: I don't care if it is from Knapsack or not, it is just, i've tried from knapsack and I couldn't Do you have any idea? – DarK_FirefoX Jan 20 '17 at 18:50
• @Zir - I read that article, and also had tried reduce it from EqualPartition but it needs the sum of the elements in the partition to be equal to a fixed $k$, and I need at most $k$. Any Idea how to get that? – DarK_FirefoX Jan 20 '17 at 18:52

Assuming that you have a set $S=\{b_1,\ldots,b_n\}$ and a number $V$ and you would like to find two subsets $X$ and $Y$ of $\{1,\ldots,n\}$ such that $\sum_{i\in X}b_i\leq V$ and $\sum_{i\in Y}b_i\leq V$ and $|X|=|Y|$.

Given an instance of EQUAL-PARTITION (EP) $E=\{a_1,\ldots,a_n\}$, are there two subsets $A$ and $B$ of $\{1,\ldots,n\}$ such that $\sum_{i\in A}a_i=\sum_{i\in B}a_i=\frac{\sum_{i=1}^na_i}{2}$ and $|A|=|B|$?

You construct an instance of your problem as follows:

$$b_i=a_i+\frac{2}{n}V-\frac{\sum_{i=1}^na_i}{n}.$$

Now, EP is solved iff your problem is solved.

• For the only if case, assume that EP is solved, that is there are two subsets $A$ and $B$ of $\{1,\ldots,n\}$ such that $\sum_{i\in A}a_i=\sum_{i\in B}a_i=\frac{\sum_{i=1}^na_i}{2}$ and $|A|=|B|$. Take $X=A$ and $Y=B$. You will find that $\sum_{i\in X}b_i=V\leq V$ and $\sum_{i\in Y}b_i=V\leq V$ and $|X|=|Y|$.
• For the if case, assume that you find two subsets $X$ and $Y$ of $\{1,\ldots,n\}$ such that $\sum_{i\in X}b_i\leq V$ and $\sum_{i\in Y}b_i\leq V$ and $|X|=|Y|$. Take $A=X$ and $B=Y$. You will find that $\sum_{i\in A}a_i\leq \frac{\sum_{i=1}^na_i}{2}$ and $\sum_{i\in B}a_i\leq \frac{\sum_{i=1}^na_i}{2}$ and $|A|=|B|$. Since $\sum_{i\in A}a_i+\sum_{i\in B}a_i=\sum_{i=1}^na_i$, you get $\sum_{i\in A}a_i=\sum_{i\in B}a_i=\frac{\sum_{i=1}^na_i}{2}$
• Reading the answer and liking it! Trying to test it properly. But, one thing! What should I use as $V$ for my problem? – DarK_FirefoX Jan 20 '17 at 20:42
• Take $V=\frac{\sum_{i=1}^{n}a_i}{2}$. – Zir Jan 20 '17 at 21:24
• According to the construction you suggested for $b_i$ then if I take $V$ like that then $a_i$ will be equal to $b_i$. So I am left with the same! But your answer got me in a direction I'm working on, I will write the answer if get to something! – DarK_FirefoX Jan 20 '17 at 21:35
• Well @Zir, Seing your answer give me an idea for the solution! The problem is I didn´t create the decision problem for my problem correctly. Aster giving thinking a bit more. My decision problem should have a value $k$ that stands for exactly how many items I should take. With that and EQUAL-PARTITION I had it. Thank you so much for your help! PS: I don´t know if I should Accept your answer or answer my self the question!? – DarK_FirefoX Jan 21 '17 at 13:07
• I think you can answer the question if this answer doesn't satisfy you. – Zir Jan 21 '17 at 19:03