0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If you want a hint, a good source problem is POSITIVE 1-in-3 SAT; it allows a quick and easy reduction to the PARTITION problem with all $a_i$s distinct and odd. Let me know if you need more details. $\endgroup$ – Marzio De Biasi Nov 13 '14 at 20:10
  • $\begingroup$ Can you please give me more details? $\endgroup$ – user24175 Nov 16 '14 at 12:18
  • $\begingroup$ I can make a reduction from positive 1-in-3-SAT, but it is a reduction only for distinct numbers, not neccessary odd! Thanks! I will be waiting for your reduction, meanwhile I will try to find a reduction on my own. $\endgroup$ – user24175 Nov 16 '14 at 18:41
  • $\begingroup$ I quickly edited it (most details are omitted); in every case I saw that daniello posted a quicker (and better) reduction from PARTITION that seems ok; it is the same trick I used to make the integers distinct and odd (the $2^{i+1}+1$ lower bits of my integers); I didn't notice that it could be applied directly to an instance of PARTITION. $\endgroup$ – Marzio De Biasi Nov 16 '14 at 20:22
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$

enter image description here

Blank cells represent $0$s

$\endgroup$
  • $\begingroup$ Oh, Thank you guys! Awesome! I actually was doing the same thing as you. My only mistake was that instead of taking only one number S, as you built here, I was taking m different numbers with a digit 1 added at the end, which in total it was adding to their summation by m, and it was a trouble! $\endgroup$ – user24175 Nov 16 '14 at 23:57
  • $\begingroup$ We don't know, but it is NP-hard (the polynomial time many one reduction proves it); so it is in P if and only if P=NP. $\endgroup$ – Marzio De Biasi Nov 17 '14 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.