0
$\begingroup$

(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?

  • 1
    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.2011-08-08
  • 1
    @C'est Moi: Profanity and insults are unacceptable here. I have deleted your comment to Gerry.2011-08-08
  • 0
    I expected as much. I apologise.2011-08-08

1 Answers 1

2

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.

  • 0
    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?2011-08-08
  • 0
    @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.2011-08-08
  • 2
    @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.2011-08-08
  • 0
    Joriki, I didn't realise it was how I asked the question, not the question itself... I suppose the answer as to why I asked this is because I am curious. I have enough familiarity with mathematics to know that a theorem stands until an exception is shown. I was attempting to predict the opposition before I studied a specific instance of the generalised Knapsack problem.2011-08-08
  • 0
    Again, I think I understand this, that is why I stated it by saying is this a legitimate Knapsack problem and so within the NP-Complete complexity class. I understand that the problem itself is not NP-Complete. This touches on the idea of weakly NP-Complete...2011-08-08
  • 0
    @C'est Moi: From how you're using the terminology, it doesn't seem to me that you understand. The example you gave is a problem instance, so it doesn't make sense to ask whether it's in the complexity class NP-complete or not. It makes sense to ask whether it's a legitimate instance of the knapsack problem, but an instance being an instance of a problem doesn't change the fact that it's the problem (meaning the problem class) and not the instance that's in a complexity class. The error is particularly evident in the formulation of your question, but still there in your above comment.2011-08-08
  • 0
    Then that is a sufficient answer. Yes it is Knapsack, but no it is not NP-Complete... are you saying even weakly NP-Complete...? Can you tell me the criteria for a knapsack problem to be considered NP-Complete? Is it the number of values in the set exceeding some amount? Or the size of the knapsack, or the size of the largest, or smallest value in the set? I appreciate the dialogue.2011-08-08
  • 0
    @C'est Moi: This has nothing to do with weak NP-completeness, which is related to how you measure the input sizes; quite the opposite, the fact that it makes a difference how you measure the input sizes only makes sense because the complexity is a property of the class and not of the instances.2011-08-08
  • 1
    @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.2011-08-08
  • 0
    D'accord. I apologise, so how about looking at it from a reduction standpoint. If I show that a problem not considered NP-Complete can be viewed as a Knapsack problem then that problem enters the NP-Complete class. The question is: is one instance enough to support the claim for reduction.2011-08-08
  • 0
    @C'est Moi: Perhaps I've been adding to the confusion by speaking of "problem classes". I did that to distinguish them from problem instances. The usual terminology is to call what I called "problem classes" simply "problems"; e.g., there is the knapsack *problem*, and you gave an example of an *instance* of this problem. The word "class" is usually used for complexity classes, i.e. entire collections of problems with a certain complexity. Perhaps best to stick to that terminology and to speak only of complexity classes, problems, and instances, keeping in mind that problems aren't instances.2011-08-08
  • 0
    Some clarification: D'accord. I apologise, so how about looking at it from a reduction standpoint. If I show that a problem not considered NP-Complete can be viewed as a Knapsack problem then that problem enters the NP-Complete class. The question is: is one instance of a problem enough to support the claim for reduction.2011-08-08
  • 0
    @C'est Moi: I'm not sure I understand that last question. If you mean whether reducing one instance of a problem to an instance of the knapsack problem is enough to show that the problem is $NP$-complete, the answer is no. You can reduce easy instances of hard problems to all sorts of easy or hard problems; that says nothing about the complexity class of the problem.2011-08-08
  • 0
    Right, but disregard the complexity class issue. I am saying if I show one instance of a problem can be viewed using the Knapsack model, does that problem become a Knapsack reduction?2011-08-08
  • 1
    @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.)2011-08-08
  • 0
    The question was is one instance enough?. You answered this. But if I can show all instances then it will be scene as a special case of the knapsack problem?2011-08-08
  • 0
    @C'est Moi: I wouldn't say "special case" because that hides the importance of the properties of the reduction itself. If you can reduce all instances of a problem to instances of the knapsack problem but the time required for actually transforming an instance is exponential in the input size, then you haven't achieved anything. As far as you're interested in the existence of polynomial-time algorithms and your reductions take polynomial time, then, yes, you can consider a problem reduced to another problem once you've found such a reduction for all problem instances.2011-08-08
  • 0
    joriki, you're taking the time to discuss this with me is paramount. Thank you very much.2011-08-08
  • 0
    @C'est Moi: You're welcome.2011-08-08