Partition problem

Question

We know that Partition problem is NP-complete:

"Given a multi-set of positive integers like X = < a_1, a_2, ... a_n >, is there any bi-partition for X such that the summation of the numbers in S and S' are equal?"

I find a reduction from the subset-sum problem into the partition problem, but is there any other proof for the NP-completeness of the subset-sum (like from 3-SAT)?

I am actually trying to see if the special case of the partition problem in which all the a_i's are odd distinct integers is NP-complete or not. Does anybody have any idea?

Answer 1

Start from the partition problem and let $a_i' = a_i * 100n^2 + 2*i + 1$. Also add in new elements $b_1', \ldots b_n'$ with $b_i' = 2i+1$. All variables are odd and distinct.

For the forward direction, suppose there is a partition of $\{a_1, \ldots a_n\}$ into two sets $L$ and $R$ such that $\sum_{a_i \in L} a_i = \sum_{a_i \in R} a_i$. Set $L' = \{a_i' : a_i \in L\} \cup \{b_i' : a_i \notin L\}$ and $R' = \{a_i' : a_i \in R\} \cup \{b_i' : a_i \notin R\}$. This is a partition with the same sum in $L'$ and $R'$

For the reverse direction, suppose there is a partition of $a_1',\ldots, a_n', b_1', \ldots b_n'$ into $L'$ and $R'$. Set $L = \{a_i : a_i' \in L'\}$ and $R = \{a_i : a_i' \in R'\}$. It is easy to verify that the sum in $L$ and $R$ is the same - since otherwise the sum of $\sum_{a_i' \in L'} a_i'$ and $\sum_{a_i' \in R'} a_i'$ differ by at least $100n^2$ and the $b_i'$s can't compensate for this.

Answer 2

There is a quick reduction from POSITIVE 1-in-3 SAT; I give you only a sketch of it.

Given a POSITIVE 1-in-3 SAT instance with $m$ positive clauses (in which every literal is unnegated) and $n$ variables; without loss of generality we can assume that the clauses are all distinct. For every variable $x_i$ add an integer $a_{x_i}$:

$a_{x_i} = \sum_{k \in I_{x_i}} 2^{3k + q} + 2^{i+1} + 1$ where $I_{x_i}$ is the set of the indices of the clauses that contain $x_i$; and $q$ is a large enough integer (for example $n+1$) that avoid the lower bits to "interfere" with the upper bits.

Add an integer $S = \sum_{k=1}^m 2^{3k + q} + 1$; add $n$ dum integers $d_i = 2^{i+q}+1, i=1...n$ and finally add $e = 1$

All integers are distinct and odd.

Suppose that $S$ is included in $A$; then, for every clause $C_j = ( x_{i_1}, x_{i_2}, x_{i_3})$, exactly one of the $a_{x_{i_1}},a_{x_{i_2}},a_{x_{i_3}}$ can be included in $A$ because there are exactly four integers with the bit $2^{3j+q}$ set to 1 (three from the elements of the clause and one from $S$) and it easy to prove that this forces a valid 1-in-3 assignment (the $a_{x_i}$s included in $A$ correspond to variables $x_i$ that are set to true and form a valid 1-in-3 assignment for the original formula). The elements $d_1,...,d_n, e$ can be used to balance the $2^{i+1}+1$ part of the corresponding $a_{x_i}$ ($e$ is used to balance the lower bit of $S$).

An example of the reduction from the POSITIVE 1-in-3 SAT formula:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_4 \lor x_5) \land (x_1 \lor x_4 \lor x_6) \land (x_2 \lor x_5 \lor x_6)$

Blank cells represent $0$s