1

I need to show that problem "partition problem 2:1" is NP-complete.

I know that I need to use $A'$ as certificate to proof that problem is NP.

I know that "partition problem": given $s: A \rightarrow \mathbb N$, find $A' \subset A : \sum_{a \in A'} s(a) = \sum_{a \in A \backslash A'} s(a)$
is NP-hard.

Using this, I want to show that my problem:
$s: A \rightarrow \mathbb N$, find $A' \subset A : \sum_{a \in A'} s(a) = 2\sum_{a \in A \backslash A'} s(a)$
is also NP-hard.

How can I reduce partition problem to "partition problem 2:1"?

Angelika
  • 69

1 Answers1

1

Starting with your definition of the normal or 1:1 partition problem:

given $s: A \rightarrow \mathbb N$, find $A' \subset A : \sum_{a \in A'} s(a) = \sum_{a \in A \backslash A'} s(a)$

Clearly you can multiply each of the members of $A$ by two and not affect the hardness or satisfiability of the problem. Call this new set of natural numbers $B$. Compute the sum of all members of $B$ and then divide the result by two. Call this result $z$ and add it as a new member of $B$.

Now, iff there is a satisfying 2:1 partition of $B$, a 1:1 partition of $A$ can be recovered from this solution by removing $z$ from the 2:1 partition of $B$ and then dividing all the remaining members of $B$'s partition by two to produce a 1:1 partition containing $A$'s values.

This scheme works for the 1:1 partition problem over any $A$ and can be done in polynomial-time. So this scheme is a polynomial-time reduction from the 1:1 partition problem to the 2:1 partition problem, proving the latter's NP-hardness.

Kyle Jones
  • 1,871