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