Subset sum is only weakly NP-hard. It has a polynomial solution not in the size of the input but rather in the value of the numbers (dynamic programming). Since

Subset sum is only weakly NP-hard. It has a polynomial solution not in the size of the input but rather in the value of the numbers (dynamic programming). Since numbers are encoded logarithmically, this algorithm is exponential in the size of the input. So, solving subset sum is only impressive if you can solve it for very large numbers.