2
$\begingroup$

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?

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.