SUBSET-SUM with binary - unary - “positional” encoding

Question

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 $<x_{1},...,x_n>$, find if the sum of one or more non-empty subset equal 0) is NP complete

If we use unary encoding $<x_{1},...,x_{n}> = 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 $<x_{1},...,x_{n}>$ 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

Answer 1

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.