9 ms·
NP-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 al
by lorenzhs 6y ago
NP-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.