Nice,

(Pseudo) run time of O(sqrt(n)*t).

Subset sum is np-complete, adds to the list of tractable-in-practice NP-complete problems.

Edit: I suppose I misunderstood - pseudo-polynomial time doesn’t contradict NP-completeness even if applies to all problems in a class.

https://en.wikipedia.org/wiki/Subset_sum_problem

A term for that class of problems, NP-complete but with a pseudo-polynomial algorithm, is weakly NP complete.

Nice,

(Pseudo) run time of O(sqrt(n)*t).

Subset sum is np-complete, adds to the list of tractable-in-practice NP-complete problems.

Edit: I suppose I misunderstood - pseudo-polynomial time doesn’t contradict NP-completeness even if applies to all problems in a class.

https://en.wikipedia.org/wiki/Subset_sum_problem

A term for that class of problems, NP-complete but with a pseudo-polynomial algorithm, is weakly NP complete.