1. 7
  1.  

  2. 1

    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

    1. 2

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