Isn't every polynomial time problem an NP problem?

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.

• And I don't mean in the sense that P=NP, I mean that they are all NP but not really P. Apr 5 '20 at 22:40
• – D.W.
Apr 5 '20 at 23:04
• I'm not quite sure what you're asking, but: are you just talking about changing our definition of "input size?" If so, then yes, changing the definition of input size changes what P and NP(-complete) mean. But I'm not sure what the point is. Apr 6 '20 at 22:26