1
$\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 a complexity class NP-Complete? I understand the concepts of weakly NP-Complete and pseudo-polynomial time...

(v) If one shows a problem to be a knapsack problem, and solves the problem with a psuedo-polynomial algorithm, is it possible that the same algorithm could not be used to solve all examples of knapsacks with limited sets of relatively small integers? If so, would this algorithm still be considered a solution to the Knapsack Problem or simply a solution to this unique instance of the Knapsack Problem?

(vI) Lastly, how important is it for the 'boxes' to have values and weights? It seems to me the subset sum, which is NP-Complete by reduction from the Knapsack Problem, only has weights and lacks the value variable? (As depicted in the wikipedia.org entry associated image)

I have read the wikipedia.org entry extensively as well as some arXiv entries on the subject and excerpts of books on Google Books along with other random online resources, but I was still left with these questions... Thank you

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ try posting at math.stackexchange.com/questions?sort=newest $\endgroup$
    – Will Jagy
    Commented Aug 7, 2011 at 22:33
  • 2
    $\begingroup$ Complexity Theory deals with families of problems. Hence, it does not even begin to make sense to say that a single instance of a problem is in NP or not. You need to get a hold of a good introductory book on complexity theory, I don't think wikipedia will be enough to learn all this. $\endgroup$
    – Thierry Zell
    Commented Aug 7, 2011 at 22:55
  • $\begingroup$ I don't think the "set-theory" tag is appropriate here. $\endgroup$
    – Quinn Culver
    Commented Aug 7, 2011 at 23:35
  • $\begingroup$ Edited tags to remove [set-theory] $\endgroup$
    – David Roberts ♦
    Commented Aug 8, 2011 at 0:10
  • 2
    $\begingroup$ Before you post to math.stackexchange, take Thierry's comment on board. $\endgroup$
    – Gerry Myerson
    Commented Aug 8, 2011 at 1:31

1 Answer 1

Reset to default
0
$\begingroup$

Let me try to give (very partial) answers. I think that your questions need some clarifications if you want more useful answers.

(i) I do not think your question is well-posed. As already mentioned in comments, you cannot fix the instance size and speak about NP-completeness. Nevertheless, you could define a new problem k-KNAPSACK where you are given a set of k integers, and where the measure of the instance size is the size of the integers that appear. My 2-cent guess is that this problem is solvable in polynomial time.

(ii) & (iii): These questions make sense, but I have no answer. The good way to find answers is to look at the reduction proving that KNAPSACK is NP-hard. (You can find it in [1] for example, but you must be able to find it via your favorite search engine.) If I am not mistaken, the reduction is a very basic one from PARTITION so you should need to look at PARTITION too, and then continue, to see whether you can modify it a bit to make your integers pairwise coprime for instance. I sort of remember that some restrictions of PARTITION still are NP-complete (though I do not remember what these are), so it should be possible to restrict a bit KNAPSACK so that it remains NP-complete. Note however that for instance if you fix a bound on the size of the integers in the set, then the problem has a polytime algorithm.

[1] Michael R. Garey and David S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, 1979.

(iv) I am not able to give a sense to this question.

(v) I am not sure what you mean by "a problem to be a knapsack problem". If you have a problem that can be reduced to KNAPSACK and if you have a good algorithm for this problem, you do not have a good algorithm for KNAPSACK: For, remember that any polynomial-time computable problem can be reduced to KNAPSACK... But in the converse sense it may work: if you can reduce KNAPSACK to a problem for which you have a pseudo-polytime algorithm, and if the reduction is very simple (when you say that a problem is a knapsack problem, it may be understood as "there exists a direct translation between both problems"), that is it is really a mere rewriting of the problem, then the algorithm should work on KNAPSACK. But once again, this really depends on what you exactly mean by "a problem to be a knapsack problem". N.B.: Speaking about pseudo-polytime does not make sense with "small instances", since an algorithm has to be able to handle with any size of input.

(vi) No importance since, as you correctly states it, if each element has the same weight as its value, this is SUBSET SUM.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Bruno, my lingering question I suppose is what criteria needs to be met to give an instance of the Knapsack Problem the complexity class NP-Complete? $\endgroup$
    – user17007
    Commented Aug 8, 2011 at 10:22
  • $\begingroup$ From the wiki : Pseudo-polynomial time : "In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input – its number of digits)." So am I reading this wrong in thinking it says that such a classification's running time depends on the number of digits, or size of values, or ... Further stating instances can run in pseudo-polynomial if the values of its digits are small enough, but nondeterministic polynomial time if the values have many digits? $\endgroup$
    – user17007
    Commented Aug 8, 2011 at 19:20

Not the answer you're looking for? Browse other questions tagged .