<p>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. </p>

<p>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'$</p>

<p>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.</p>

CC BY-SA 3.0
2014-11-16T18:48:49.057Z
2014-11-16T18:48:49.057Z
daniello
<p>There is a quick reduction from POSITIVE 1-in-3 SAT; I give you only a sketch of it.</p>

<p>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}$:</p>

<p>$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.</p>

<p>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$</p>

<p>All integers are distinct and odd.</p>

<p>Suppose that $S$ is included in $A$; then, for every clause $C_j = ( x_{i_1}, x_{i_2}, x_{i_3})$, <em>exactly one</em> 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$).</p>

<p>An example of the reduction from the POSITIVE 1-in-3 SAT formula:</p>

<p>$(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)$</p>

<p><img src="https://i.sstatic.net/XKJP8.png" alt="enter image description here"></p>

<p>Blank cells represent $0$s</p>

CC BY-SA 3.0
2014-11-16T23:57:36.077Z
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!
user24175
CC BY-SA 3.0
2014-11-17T15:10:32.443Z
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.
Marzio De Biasi
CC BY-SA 3.0
2014-11-16T16:31:37.143Z
2014-11-16T20:09:24.973Z
2014-11-16T20:09:24.973Z
Marzio De Biasi
<p>We know that Partition problem is NP-complete: </p>

<p>"Given a multi-set of positive integers like X = &lt; 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?"</p>

<p>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)?</p>

<p>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?</p>

CC BY-SA 3.0
2014-11-13T20:10:53.807Z
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.
Marzio De Biasi
CC BY-SA 3.0
2014-11-16T12:18:53.697Z
Can you please give me more details?
user24175
CC BY-SA 3.0
2014-11-16T18:41:23.810Z
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.
user24175
CC BY-SA 3.0
2014-11-16T20:22:25.767Z
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.
Marzio De Biasi
<cc.complexity-theory>
Partition problem
user24175
# Partition problem

(Asked by: username_0 on 2014-11-13)

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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: Can you please give me more details?  
> **username_0**: 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.  
> **username_1**: I quickly edited it (most details are omitted); in every case I saw that username_2 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.  

---

## 2 answers

### Answer by username_2 on 2014-11-16. Score: 2

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 by username_1 on 2014-11-16. Score: 1

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](https://i.sstatic.net/XKJP8.png)

Blank cells represent $0$s

> **Comments:**
> **username_0**: 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!  
> **username_1**: 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.  

---

