6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Hi @Vor, here in TCS SE we have LaTeX support, so maybe you would like to edit your question (by pressing the edit button above) with '$' sign inserted, which makes the question more readable. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 14 '11 at 18:03
13
$\begingroup$

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.

$\endgroup$

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.