3 ms·

There are no reasonable known lower bounds for knapsack beyond "you must at the very least spend Omega(n) time reading read the entire input". For sorting too,

There are no reasonable known lower bounds for knapsack beyond "you must at the very least spend Omega(n) time reading read the entire input". For sorting too, actually. The famous n log n bound comes from the decision tree complexity, which in turn assumes that only comparison queries can be made ("is A > B?"). However, many domains give more flexibility than just comparison queries, and in particular there are known O(n log log n)-time sorting algorithms for integers (see, for example, https://dl.acm.org/doi/10.1145/509907.509993 https://dl.acm.org/doi/10.1145/509907.509993 ). While one can come up with contrived domains with arbitrarily large lower bounds (all the way up to computability-centered shenanigans like "sort these Turing machines by how long they take to halt on the empty tape, with ties broken by a lexicographical ordering"), most useful ones not derived from EXPTIME-hard problems tend to have no known lower bound better than just linear.

tsimionescu 5y ago
> The famous n log n bound comes from the decision tree complexity, which in turn assumes that only comparison queries can be made ("is A > B?"). However, many domains give more flexibility than just comparison queries, and in particular there are known O(n log log n)-time sorting algorithms for integers (see, for example, https://dl.acm.org/doi/10.1145/509907.509993 https://dl.acm.org/doi/10.1145/509907.509993 ). Sure, for specific subclasses of a problem there are sometimes known better algorithms than the more universal bounds, and there is nothing to say the same can't be true for knapsack. I said this in my other comment, but the most interesting example I am aware of is the Simplex algorithm, whose worse-case complexity is exponential, but which is (deterministically) polynomial for "most" classes of input. Anyway, interesting to know that lower bounds for NP-complete problems are not known, thanks for explaining this. Thinking about it, it does make sense, especially if the correct lower bound actually has to be non-polynomial, but I had incorrectly assumed otherwise.
- CaptainNegative 5y ago
  The simplex method is an algorithm for solving LPs; the comparison of a particular algorithm's running time to the complexity of a problem isn't exactly one-to-one. In this particular case, there are algorithms with polynomial-time worst-case guarantees for solving the same problem as simplex, including the classical ellipsoid method and a whole battery of interior point methods. The only technique complexity theorists have at the moment for finding unconditional lower bounds for a problem's running time is diagonalization, as in the method used for proving the time hierarchy theorem. While this can be used to prove that some problems require exponential time to solve, it is provably too weak to separate P from PSPACE, let alone P from NP. But it is enough to separate P from EXPTIME, meaning that any EXPTIME-hard problem such as Generalized Chess is provably not in P. The point you touch on with Simplex is interesting, because as you mentioned it works extremely well in practice despite the well-studied lower bounds. There is some line of work that tries to explain it with "Smoothed Complexity" analysis, but despite the polynomial bound the current results are still not terribly satisfying. More generally, I think you were hypothesizing something along the lines of Imagliazzo's "Heuristica" (see https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multiverse/ https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multi... ), where NP-hard problems are hard in the worst case but actually finding these hard instances is equally difficult. This is a very real scenario, with both pros (we can solve stuff!) and cons (hackers can too!), at least on a theoretical level where "solvable" is synonymous with "polynomial time solvable". I think this is considered the third most likely of the five hypothesized worlds after Cryptomania and Mini-crypt.

tsimionescu 5y ago

> The famous n log n bound comes from the decision tree complexity, which in turn assumes that only comparison queries can be made ("is A > B?"). However, many domains give more flexibility than just comparison queries, and in particular there are known O(n log log n)-time sorting algorithms for integers (see, for example, https://dl.acm.org/doi/10.1145/509907.509993 https://dl.acm.org/doi/10.1145/509907.509993 ). Sure, for specific subclasses of a problem there are sometimes known better algorithms than the more universal bounds, and there is nothing to say the same can't be true for knapsack. I said this in my other comment, but the most interesting example I am aware of is the Simplex algorithm, whose worse-case complexity is exponential, but which is (deterministically) polynomial for "most" classes of input. Anyway, interesting to know that lower bounds for NP-complete problems are not known, thanks for explaining this. Thinking about it, it does make sense, especially if the correct lower bound actually has to be non-polynomial, but I had incorrectly assumed otherwise.

CaptainNegative 5y ago
The simplex method is an algorithm for solving LPs; the comparison of a particular algorithm's running time to the complexity of a problem isn't exactly one-to-one. In this particular case, there are algorithms with polynomial-time worst-case guarantees for solving the same problem as simplex, including the classical ellipsoid method and a whole battery of interior point methods. The only technique complexity theorists have at the moment for finding unconditional lower bounds for a problem's running time is diagonalization, as in the method used for proving the time hierarchy theorem. While this can be used to prove that some problems require exponential time to solve, it is provably too weak to separate P from PSPACE, let alone P from NP. But it is enough to separate P from EXPTIME, meaning that any EXPTIME-hard problem such as Generalized Chess is provably not in P. The point you touch on with Simplex is interesting, because as you mentioned it works extremely well in practice despite the well-studied lower bounds. There is some line of work that tries to explain it with "Smoothed Complexity" analysis, but despite the polynomial bound the current results are still not terribly satisfying. More generally, I think you were hypothesizing something along the lines of Imagliazzo's "Heuristica" (see https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multiverse/ https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multi... ), where NP-hard problems are hard in the worst case but actually finding these hard instances is equally difficult. This is a very real scenario, with both pros (we can solve stuff!) and cons (hackers can too!), at least on a theoretical level where "solvable" is synonymous with "polynomial time solvable". I think this is considered the third most likely of the five hypothesized worlds after Cryptomania and Mini-crypt.