3
$\begingroup$

In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$.

The problem is obviously in NP. I am trying to prove that it is NP-complete.

So far, I have found the following reduction from the standard Partition problem (which is the same problem but without the restriction on the number of integers). Given an instance $I$ of Partition with some $n$ integers, do for $k$ in $0,1,\ldots,n-1$:

  • Add $k$ zeros to $I$ ;

  • If $n+k$ is even, then try to find a balanced partition.

    • If a balanced partition is found, remove the zeros and return it.

If no partition is found for any $k$, return "No partition".

The algorithm is correct since, if a solution to the original instance $I$ exists, then we can add some $k$ zeros to one of the parts to get a balanced partition, so for this $k$, a balanced partition will be found.

This shows that Balanced Partition cannot be solved in polynomial-time unless P=NP. However, it does not show that the problem is NP-complete; according to this Wikipedia page, "a problem is NP-complete if it belongs to NP and all problems in NP have polynomial-time many-one reductions to it", while the reduction I just described is not a many-one reduction - it is a Cook reduction.

EDIT: this paper shows that completeness under Cook reduction is (under some assumptions) distinct than completeness under many-one (Karp-Levin) reductions (see also this cstheory.SE question).

Question: How can I prove that Balanced-Partition is NP-complete under a many-one reduction?

$\endgroup$

2 Answers 2

2
$\begingroup$

Instead of adding $k$ zeros for $k$ in $0,1,\ldots,n-1$, just adding $n$ zeros is enough. It is somewhat funny the reduction in the question is just one-off the right reduction.


Here is the detail. It is quite easy.

Let us reduce the partition problem, which is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets with equal sum, to this "balanced partition problem".

Suppose $I=\text{multset}\{a_1, a_2, \cdots, a_n\}$, $a_i>0$ is (the input of) an instance of the partition problem.

Let $I'=\text{multset}\{a_1, a_2, \cdots, a_n, a_{n+1}=0, a_{n+2}=0, \cdots, a_{2n}=0\}$, i.e., $I$ with $n$ zeros added. $I'$ is an instance of the balanced partition problem.

  • Suppose $I$ is a yes instance, i.e., there exists $I\subseteq\{1,2,\cdots, n\}$ such that $$\sum_{i\in I}a_i=\sum_{1\le i\le n,\,i\notin I}a_i.$$ Then $$\sum_{i\in J}a_i=\sum_{1\le i\le 2n,\,i\notin J}a_i,$$ where $J=I\cup\{i\mid n+1\le i\le 2n-|I|\}$. Since $|J|=2n/2$, we know $I'$ is a yes instance.
  • Suppose $I'$ is a yes instance, i.e., there exists $J\subseteq\{1,2,\cdots, 2n\}$ such that $|J|=n$ and $$\sum_{i\in J}a_i=\sum_{1\le i\le 2n,\,i\notin J}a_i.$$ Removing all items that are $0$ from both sides, we obtain an equality that says $I$ is a yes instance.

The mapping from $I$ to $I'$ is a polynomial-time many-one reduction (a.k.a Karp reduction) from the partition problem to the balanced partition problem. (In fact, it is one-to-one reduction; however, "many-one" is good enough.) Since the former is $\mathsf{NP}$-complete and the latter is in $\mathsf{P}$, the latter is $\mathsf{NP}$-complete as well.

$\endgroup$
0
-1
$\begingroup$

It sounds like you may already know the answer to your first question - the definition of NP-completeness requires you to find a many-one reduction, so no, you have not proven it to be NP-complete, but you have proven that if P!=NP then there is no polynomial-time algorithm for it. See also https://en.wikipedia.org/wiki/NP-completeness#Completeness_under_different_types_of_reduction.

$\endgroup$
1

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.