I found this question in my Optimization Algorithm course, the full question is this: If we can prove all Knapsack problems with capacity limited to 100 can be solved in polynomial time, then all Knapsack problems belong to P. Is this sentence true or false? Justify.
With my book and some research I came out with something like this: First of all KP is an NP-complete problem. With Dynamic programming it can reach a pseudopolynomial time, but it's not enough. If, absurdly, we can prove that KP with capacity limited to 100 can be solved in polynomial time then we can assume that KP belongs to P.
What do you think about my answer? I think the absurd is not so right in the last sentence.
Proving that all knapsack problems with a limited capacity can be solved in polynomial time does not prove that all knapsack problems are in P. If a problem is in P, that means that it can be solved in polynomial time. This means that it can be solved in O(n^k) where k is some integer. Big O is an upper bound, meaning that, if an algorithm is O(n), as n approaches infinity, the time it takes to do the algorithms will never be longer than n. By proving that all problems with n<100 can be solved in polynomial time, this makes no guarantee for much larger n. Therefore we cannot say that there is an algorithm that runs in O(n^k) and is therefore in P.