3 ms·

Is there any proof that the solution must have an iterative approach? For instance, say there was some extremely clever way of depicting the relationships that

Is there any proof that the solution must have an iterative approach? For instance, say there was some extremely clever way of depicting the relationships that allowed a "single pass" computation in a way that abstractly solves it that can be reduced to the valid combinations without ever having to "guess" or backtrack or do some variation of a permutation map wherein you reduce a set of candidate solutions. This novel method would solve it like say, one does with the process of algebra. Of course this would be in some rules and abstractions perhaps invented and defined solely for this problem - perhaps discarding all of arithmetic in the process. I can imagine a proof could exist showing such an approach isn't possible and I realize coming up with such a novel system for this problem is so unlikely the inventor would be put in the league of Gauss and Maxwell, the question is setting that aside, has it been shown to be a futile effort?

Cerium 5y ago
This is a variation on the Knapsack problem. I'm not familiar with the common proofs used, but it is a well studied problem.
- kristopolous 5y ago
  Yep, that's kind of why I asked it. I've always been unhappy with the various solutions and I've felt that with some representations, abstractions, and relationships this class of problems would be as solvable as say, a geometry problem. But it might be the geometry problem of squaring the circle and I can roughly see how a proof for it having to be iterative might work (by contradiction specifically). I am not enough of a mathematician in the field to know
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 ago
  The 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 ago
    The 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 ago
  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.

Cerium 5y ago

This is a variation on the Knapsack problem. I'm not familiar with the common proofs used, but it is a well studied problem.

kristopolous 5y ago
Yep, that's kind of why I asked it. I've always been unhappy with the various solutions and I've felt that with some representations, abstractions, and relationships this class of problems would be as solvable as say, a geometry problem. But it might be the geometry problem of squaring the circle and I can roughly see how a proof for it having to be iterative might work (by contradiction specifically). I am not enough of a mathematician in the field to know

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 ago
The 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 ago
  The 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 ago
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.