3 ms·

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 a

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]