# Knapsack Problem And Computational Complexity

(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9}

(ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, 3, 9, 81 } (essentially powers of 3)

(iii) Is there any limitations on the relationship between the numbers of the set and the size of the knapsack?

(iv) If I were to make my own knapsack problem what strict criteria must I follow? For instance, is a knapsack of 3, and the set {1, 5, 6, 2} a legitimate knapsack problem? Meaning this example has the complexity class NP-Complete?

-
When you posted this question to MathOverflow you were given a helpful comment which you appear to have completely ignored. So: THE NP=COMPLETE TERMINOLOGY DOES NOPT APPLY TO INDIVIDUAL INSTANCES OF THE KNAPSACK PROBLEM. –  Gerry Myerson Aug 8 '11 at 7:30
@C'est Moi: Profanity and insults are unacceptable here. I have deleted your comment to Gerry. –  Zev Chonoles Aug 8 '11 at 12:46
I expected as much. I apologise. –  C'est Moi Aug 8 '11 at 13:39

@Nicholas: Perhaps what's confusing you is that the example is easy to solve and you're wondering how it can be in a hard class of problems? It's important to understand that complexity is a property only of the problem class, not of the problem instances; for instance, a regular $n$-gon is a valid instance of the traveling salesman problem, which is trivial to solve; but TSP as a class is NP-complete. If you look at the definition of NP-completeness, it doesn't make sense to apply it to an individual problem instance; it talks about how the effort grows with the size of the instances. –  joriki Aug 8 '11 at 6:53