0
$\begingroup$

The SUBSET SUM decision problem consists of poitive integers a1,...,an; b.
We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$

I want to prove that if b is given in unary(and the ai's are gives in binary), that this decision problem is in P

$\endgroup$
3
0
$\begingroup$

Start by initializing a boolean array $T$ with indices from $0$ to $b$, inclusive. $T_0$ starts as true (because you can always achieve a sum of 0) and the rest of the array starts as false.

For each value $a_i$, we update the array by going though each value $x$ where $x+a_i\leq b$, and setting $T_{x+a_i}$ to true only if $T_x$ is true.

Essentially, at any point, the array describes which sums are possible using only the values of $a$ which have already been looked at. When a new $a_i$ is looked it, any value that can be made by adding $a_i$ to a currently possible sum becomes possible.

The final decision simply involves checking if $T_b$ is true.

The bulk of the program involves iterating over all $n$ values of $a$ and all $b$ elements of the array, for a total runtime of $O(nb)$. The size of the input is at least $n+b$, because it describes each value of a $a$, and $b$ is written in unary.

Because $O(nb)$ is polynomial with respect to $n+b$, the described problem can be decided in polynomial time.

$\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.