Proof that "partition problem in proportion 2:1" is NP-complete 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"?
 A: 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.
