4 ms·
Isn't the Knacksack problem hard and unsolved problem?
by peterhil 6y ago
Isn't the Knacksack problem hard and unsolved problem?
- lorenzhs 6y agoSolving the Knapsack problem is pretty easy, it's probably the textbook example for explaining branch-and-bound algorithms. What you probably had in mind is that it's NP-complete, meaning that we don't know any polynomial-time algorithms and most experts think that none can be found, although nobody has been able to prove that (this is the famous P=NP? problem).
- qsort 6y agoWhich is why the OP says: > Find counterexamples to each of the following algorithms for the knapsack problem. Anyway, yes, in the strictest sense of the term, it is unsolved because it's NP-complete, however it's been thoroughly analyzed in many different ways (it's pseudo-P, we have a MITM algo, different flavors of approximations, etc.)
- lorenzhs 6y agoNP-complete doesn't mean unsolvable! It means that we don't know any algorithms that run in subexponential time for every input. But of course we can use the algorithms with exponential worst case running time. We can also use algorithms that solve most instances fairly quickly but may take a very long time to solve some particularly hard instances.
- qsort 6y agoYes, I don't disagree with any of this. Let me rephrase that. The problem of determining what is the minimum asymptotic time complexity for an algorithm that correctly solves any knapsack instance is unsolved.
- hansvm 6y agoExponential != Super-polynomial There exist np-complete problems with known super-polynomial, sub-exponential solutions. The stable set problem for planar graphs is an example.
- howling 6y agoActually, the knapsack problem allows taking an item more than once. The problem described in the blog is the 0-1 knapsack problem which can be solved in polynomial time.