# 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

## 1 Answer

You tell us! :-) How are we supposed to know what problem you're dealing with? If you're talking about what's usually called the knapsack problem, you can easily find the answers to your questions at Wikipedia; there's no mention of coprimality, similarity or any other restrictions on the numbers or their number there. Regarding your last question, complexity is a property of a problem class, not of problem instances.

-
I think I understand this, what I am asking is what makes a problem considered a member of a class? Classes are formed when so many problems share certain aspects. I am asking what are those shared aspects. I read the wiki. The reason I am asking here is because it doesn't mention coprimality, similarity or any other restrictions. Judging by your response I deduce that yes the examples above are fine for Knapsack consideration, because as you said, the wiki doesn't say anything to the contrary? –  C'est Moi Aug 8 '11 at 6:43
@Nicholas: If it doesn't mention those restrictions, why do you think they might apply? I'd understand a question of the form "Wikipedia doesn't mention coprimality, but it seems to me coprimality should be a condition because..." -- but why wonder about arbitrary restrictions when you've already read the problem definition and there's no mention of or reason for them? Yes, those examples are fine. –  joriki Aug 8 '11 at 6:47
@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
@C'est Moi: From your last comment, I'm now certain that you don't understand the concept of a complexity class. I suggest to review the definition for that. I'm not saying that this instance isn't NP-complete, nor is it possible to specify criteria for it being considered NP-complete; what I'm saying is that it is simply not meaningful to ask whether a problem instance is NP-complete, since NP-completeness is a property of problem classes, not of problem instances. There is no contradiction here with the fact that this problem instance belongs to a problem class which is NP-complete. –  joriki Aug 8 '11 at 7:06
@C'est Moi: To get anywhere with these things, you're going to have to get into the habit of using terminology precisely. I don't know how to make sense of "does that problem become a knapsack reduction". Yes, you have reduced one instance of the problem to an instance of the knapsack problem; no, you have not reduced all instances of the problem to instances of the knapsack problem; therefore, you have not reduced the problem itself to the knapsack problem. (Also to imply anything about NP-completeness, the reduction itself would have to be polynomial with polynomial input size mapping.) –  joriki Aug 8 '11 at 7:29