3 ms·
Given that this problem is the knapsack problem, which is known to be NP-hard, your question amounts to asking if we know for sure that P!=NP, except that you'r
by tsimionescu 5y ago
Given that this problem is the knapsack problem, which is known to be NP-hard, your question amounts to asking if we know for sure that P!=NP, except that you're actually asking for a much tighter bound than polynomial complexity.
Right now there is no proof that there isn't a polynomial time algorithm for the problem. I'm not 100% sure, but there are probably proofs for lower bounds, forbidding something like the O(n) you're thinking about. For example, the minimum possible worse-case complexity for an algorithm sorting n numbers is proven to be O(n*log n) comparisons. You're not going to find a solution to the knapsack problem that's easier than that, I think that much is obvious.
- kristopolous 5y agoThe theorized solution could create a fissure between this and other problems that's not currently recognized. Showing that they're not actually as equivalent as we thought is one of the things that's on the table here. If we were to introduce a new analytical dimensionality to things, new categories would form and there's no guarantee that the same relationships between problems would exist thereafter. Unless, that is, this has been shown to be not possible here
- tsimionescu 5y agoThe proof that knapsack is NP complete is constructive - there is a known way to translate any NP complete problem to an equivalent knapsack problem (in polynomial time). If you can then solve that knapsack problem using any method whatsoever, you can convert the result back into the result of the other NP problem you started out with, in polynomial time. So no, there is no way to redefine Knapsack so that it is not NP complete. Finding an easy solution to knapsack, however you did it, would prove P = NP. There is much more room for questions about particular classes of instances of Knapsack. Perhaps all versions of knapsack with certain physically plausible properties can in fact be solved in O(n), even if the general case can't. The Simplex algorithm is famous for having this property - in the general case it is not even NP (it is in EXP I believe), but there are whole classes of instances, including most instances found of practical interest, can be solved with a simple quadratic (?) algorithm.
- deleted 5y ago[deleted]
- CaptainNegative 5y agoThere 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 agoThe 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.