1. 7
  1. 1


    (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.


    1. 2

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