Subset sum can be solved with dynamic programming in pseudopolynomial time O(mn) which is subexponential. And, of course, subset sum problem is NP-complete. Why doesn't that contradict the Exponential time hypothesis?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Possible duplicate. cs.stackexchange.com/questions/71161/… $\endgroup$ – sunnytheit Mar 20 '18 at 6:19
-
$\begingroup$ The dynamic programming algorithm runs in exponential time. $\endgroup$ – Yuval Filmus Mar 20 '18 at 6:43
-
3$\begingroup$ Possible duplicate of How is the Subset Sum Problem NP-Complete? $\endgroup$ – xskxzr Mar 20 '18 at 8:12
Add a comment
|
