# IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

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

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.