time complexity and big O notation of sub set dynamic programming

Question

given set of $n$ positive integers and a target number $T$ there is an dynamic programming algorithm that run in $O(n T)$ time complexity that solves the sub-set sum problem, It is regarded as exponential in terms of $T$, when $T$ is a big number, for the sake of this question assume that there is an algorithm that solves sub-set sum in $O(n \ln {T})$ time complexity, does the algorithm still runs in exponential time and why ? or does it runs in polynomial time(that will put sub-set sum in P) and why ?

I am leaning toward the polynomial time algorithm since you need $O(\ln {T})$ time at least for writing $T$ digits in the memory !! I might be very wrong !!

Thanks in Advance.

Answer 1

The standard algorithm with time $O(nT)$ isn't exponential in terms of $T$, it's exponential in terms of input length, as instance with input $T$ (and $n$ numbers $\leq T$ each) has length $O(n\log T)$.

The theoretical algorithm with complexity $O(n \log T)$ would run in polynomial time of input size.