<p>If an instance of POSITIONAL-SUBSET-SUM has input length $N$, then each integer in the set $\{x_1, x_2, ..., x_n\}$ must satisfy $|x_i| \le N$, and the set itself must have size $n \le N$.  So the input length for the corresponding instance of UNARY-SUBSET-SUM is $O(N^2)$, and it is easy to see that mapping one input format to the other can be done in polynomial time.  Therefore, since UNARY-SUBSET-SUM $\in \text{P}$, we have POSITIONAL-SUBSET-SUM $\in \text{P}$ as well.</p>

CC BY-SA 2.5
2011-01-14T18:37:24.370Z
2011-01-14T18:37:24.370Z
mjqxxxx
<p>I don't know if my question is too simple (I'm not an expert, so feel free to delete it)</p>

<p><strong>SUBSET-SUM</strong> (given a set of integers $&lt;x_{1},...,x_n&gt;$, find if the sum of one or more non-empty subset equal 0) is NP complete</p>

<p>If we use unary encoding $&lt;x_{1},...,x_{n}&gt; = 0^{x_{1}}1...0^{x_{n}}1$ we fall back in P (<strong>UNARY-SUBSET-SUM</strong>)<br>
Proof: if m is the initial length of the unary input, reduce input size to $log(m)$ switching to binary representation -&gt; simulate a nondeterministic TM that solves the SUBSET-SUM in polynomial (linear) time $O(log(m))$ -&gt; the simulation is $O(2^{log(m)})$ -&gt; welcome in P .</p>

<p>But if we map $&lt;x_{1},...,x_{n}&gt;$ to a number N in which each bit "positionally" represents $x_{i}$, i.e.<br>
if $x_{i} = -1$ then set bit 0<br>
if $x_{i} = 1$ then set bit 1<br>
if $x_{i} = -2$ then set bit 2<br>
if $x_{i} = 2$ then set bit 3<br>
... and so on (for example we encode the subset $&lt;-1,-2,2,4&gt;$ with $10110001$ (bit 0 is on the left), the subset $&lt;1,3,-4&gt;$ with $0100011$, ...)<br>
(perhaps the simplest enumeration of finite subsets of $Z$) ... I'll call it <strong>POSTIONAL-SUBSET-SUM</strong> (perhaps it has another name :-)</p>

<p>It seems that we cannot apply the same strategy used to prove that UNARY-SUBSET-SUM is in P
(for some inputs switching from "positional" to binary representation expands the input)</p>

<p>So, my question: is POSITIONAL-SUBSET-SUM in P ?<br>
If not ... is POSITIONAL-SUBSET-SUM NP-complete ?</p>

<p>Thank you in advance,<br>
Vor</p>

CC BY-SA 2.5
2011-01-14T18:03:46.833Z
Hi @Vor, here in TCS SE we have [LaTeX support](http://meta.cstheory.stackexchange.com/q/3/1800), so maybe you would like to edit your question (by pressing the edit button above) with '$' sign inserted, which makes the question more readable.
Hsien-Chih Chang 張顯之
<cc.complexity-theory><subset-sum>
SUBSET-SUM with binary - unary - "positional" encoding
Marzio De Biasi
# SUBSET-SUM with binary - unary - "positional" encoding

(Asked by: username_0 on 2011-01-14)

I don't know if my question is too simple (I'm not an expert, so feel free to delete it)

**SUBSET-SUM** (given a set of integers $$, find if the sum of one or more non-empty subset equal 0) is NP complete

If we use unary encoding $ = 0^{x\_{1}}1...0^{x\_{n}}1$ we fall back in P (**UNARY-SUBSET-SUM**)  
Proof: if m is the initial length of the unary input, reduce input size to $log(m)$ switching to binary representation -> simulate a nondeterministic TM that solves the SUBSET-SUM in polynomial (linear) time $O(log(m))$ -> the simulation is $O(2^{log(m)})$ -> welcome in P .

But if we map $$ to a number N in which each bit "positionally" represents $x\_{i}$, i.e.  
if $x\_{i} = -1$ then set bit 0  
if $x\_{i} = 1$ then set bit 1  
if $x\_{i} = -2$ then set bit 2  
if $x\_{i} = 2$ then set bit 3  
... and so on (for example we encode the subset $<-1,-2,2,4>$ with $10110001$ (bit 0 is on the left), the subset $<1,3,-4>$ with $0100011$, ...)  
(perhaps the simplest enumeration of finite subsets of $Z$) ... I'll call it **POSTIONAL-SUBSET-SUM** (perhaps it has another name :-)

It seems that we cannot apply the same strategy used to prove that UNARY-SUBSET-SUM is in P
(for some inputs switching from "positional" to binary representation expands the input)

So, my question: is POSITIONAL-SUBSET-SUM in P ?  
If not ... is POSITIONAL-SUBSET-SUM NP-complete ?

Thank you in advance,  
Vor

**Tags:** cc.complexity-theory, subset-sum

> **Comments:**
> **username_1**: Hi @Vor, here in TCS SE we have [LaTeX support](http://meta.cstheory.stackexchange.com/q/3/1800), so maybe you would like to edit your question (by pressing the edit button above) with '$' sign inserted, which makes the question more readable.  

---

## 1 answers

### Answer by username_2 on 2011-01-14. Score: 13 | Accepted answer

If an instance of POSITIONAL-SUBSET-SUM has input length $N$, then each integer in the set $\{x\_1, x\_2, ..., x\_n\}$ must satisfy $|x\_i| \le N$, and the set itself must have size $n \le N$. So the input length for the corresponding instance of UNARY-SUBSET-SUM is $O(N^2)$, and it is easy to see that mapping one input format to the other can be done in polynomial time. Therefore, since UNARY-SUBSET-SUM $\in \text{P}$, we have POSITIONAL-SUBSET-SUM $\in \text{P}$ as well.


---

