See here. Knapsack problem -- NP-complete despite dynamic programming solution?

The only reason Knapsack problem is NP-complete is because input comes as binary numbers so n is actually 2^n. Since the weight is an axis of the DP array.

Then for every single problem, for example one that requires an O(n) loop through an O(n) sized array, if we consider the array to actually be 2^n bits long or something towards that effect that actually makes sense, aren't all of those problems actually NP-complete?

This seems to me like the original "feeling/intuition" of relatively middling test cases for NP problems not even working, is thrown off because then almost every algorithm ever is NP.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.