If unary subset sum problem is in P, why isn't the regular subset sum problem? Couldn't you just solve it the same way as the unary one?

Question

If unary subset sum problem is in P, why isn't the regular subset sum problem? Couldn't you just solve it the same way as the unary one?

Answer 1

Polynomial time is measured with respect to the size of the input. Let $n$ be the size of our unary input. Then polynomial time is $\text{poly}(n)$. For the unary case, we can enumerate all $2^{O(\log n)} = \text{poly}(n)$ subsets.

In the case of binary inputs, the size of the input is $O(\log n)$, and so such an algorithm takes exponential time relative to the size of the input.