4 ms·

I used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? M

I used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.

zeroonetwothree 3y ago
Much of theoretical CS is just math and has no real practical consequences. Once in a while you do encounter something useful but it’s rare.
- klyrs 3y ago
  Many NP-complete problems and their Harder variants are in the realm of optimization. Packing boxes in air freight 1% tighter can have millions of dollars of practical consequences per year. Communications and electrical networks depend on the Steiner tree problem. Machine shops, restaurants, etc leave money on the table when their schedules are not well-optimized. I could go on and on.
  - affinepplan 3y ago
    yes but theoretical advancements in NP-complete problems very rarely turn into empirical improvements
    - ethanwillis 3y ago
      It's not hard to see why this would be the case when the culture seems to start with the premise of "it's just ivory tower mathematics with no practical consequences" If instead people were willing to set that hubris to the side and treat problems seriously then maybe we would see theoretical advancements be turned into empirical improvements with proper investment. Why would investment be made to operationalize theoretical advancement if the belief is that it's meaningless? The entire reasoning of not treating these problems seriously from the start, then saying they rarely turn into empirical improvements... it all seems very self-fulfilling and circular.
  - bjourne 3y ago
    There are polynomial-time approximation schemes for all those problems. Few of the NP-complete problems are both difficult to approximate and have practical use cases. 3SAT is the big exception.
    - klyrs 3y ago
      Steiner tree problems are particularly vexatious in that regard. Polynomial-time approximation only guarantees a solution at most 40% more expensive than optimal. When you're spending tens to hundreds of millions of dollars on an electrical grid, that's quite the differential.
    - CaptainNegative 3y ago
      I don't know which airlines are packing one-dimensional bins :). In dimensions 2 and above, bin packing has no PTAS unless P=NP, and in particular it's hard to derive anything with an approximation ratio appreciably better than sqrt(num_dimensions)). And the famous Steiner tree result holds only in highly structured metrics like the Euclidean plane and some minor generalizations. For general metrics there's a lower bound of around 1.01 unless P=NP.
      - bjourne 3y ago
        Multi-dimensional bin packing in general does not have PTASes. However, for the constrained versions of the problem used in practice, PTASes and other tractable algorithms exist. Same with the STP - very difficult in non-Euclidean space, but all practical applications are in Euclidean spaces.
- deleted 3y ago
  [deleted]
ackbar03 3y ago
I did a fix on some open source tool that was pretty fancy and had the same operational complexity. But then I realized oh sht, it's now two times slower
CJefferson 3y ago
In my experience of NP-complete research, there tends to be “real world bias”. There are problems we can mostly solve in polynomial time, and those gets lots of study and people talk about them a lot. There are other problems which are equally valid np-complete problems, for example reversing most encryption and hashing algorithms (with hashes you obviously don’t get a unique reversal, but you can get something), which we generally don’t discuss, as they are entirely unsolvable in practice.
- bawolff 3y ago
  Finding a hash pre-image is kind of an artificial problem, because hash algorithms are specificly chosen to make that hard. I would assume those things are not np-complete and just np.
H8crilA 3y ago
If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. No post-quantum variants, I mean there's nothing at all. Also, if P=NP quantum computers are probably not useful at all, perhaps they're a bit cheaper, that's all. There's a lot of NP-hard problems that you'd love to solve if you could, but you avoid them because you immediately know it's not possible. For example, you could create optimal neural networks that might be 10x? 100x? more powerful for the same size/cost as GPT-4 is. This stuff is likely so beyond the reach of today's knowledge that it would be like talking about quantum mechanics and integrated circuits running at GHz speed to Euclides. It's like when Paul Erdős talked about the Collatz conjecture: "Mathematics may not be ready for such problems."
- enriquto 3y ago
  > If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. Why do you say that? A problem being in P does not necessarily mean that it's easy, or that it is solvable at all in practice. Recall that the class P contains problems that require a running time of O(n^A(6,6)), where A is the Ackerman function. This is an inconceivably large number, and there's no realistic expectation to solve such a problem for even minuscule values of n, like n=2 or 3. The class P is huge, and our puny linear and quadratic algorithms can only solve its lower, trivial levels. We have not yet started scratching the surface of the enormous set P, yet some of us are arrogant enough to call all of it "easy". For all we know, it may well be that P=NP but have no practical consequences whatsoever.
- yeeniee 3y ago
  >If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. I don't see how that follows. A polynomial can still have factors or constants on the orders of "not in this universe's lifetime", so for all practical purposes it doesn't matter.
Ar-Curunir 3y ago
Complexity theory doesn't need to have practical applications to be exciting (though it has often led to such practical applications). Complexity theory explores the fundamental nature of computation: what is and isn't feasible. It's a window into how the universe works, and so it's exciting in the same way that, say, general relativity or quantum mechanics is.
chriswarbo 3y ago
> Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics. We need to be careful when distinguishing a "problem" (e.g. SAT) and an "instance of a problem" (e.g. "is this formula satisfiable?"). Heuristics can often help us solve real-world problem instances (e.g. seat planning for this wedding; a Hamiltonian path for this salesman; etc.), at least approximately/close-enough-to-be-useful. However, we must give resource bounds to such implementations (e.g. a timeout), since there's no way to know/check if a given instance will have worst-case behaviour until we run it. What I find fascinating is that we can prove that some problems are just as hard to solve approximately as they are to solve optimally! https://en.wikipedia.org/wiki/Hardness_of_approximation https://en.wikipedia.org/wiki/Hardness_of_approximation

zeroonetwothree 3y ago

Much of theoretical CS is just math and has no real practical consequences. Once in a while you do encounter something useful but it’s rare.

klyrs 3y ago
Many NP-complete problems and their Harder variants are in the realm of optimization. Packing boxes in air freight 1% tighter can have millions of dollars of practical consequences per year. Communications and electrical networks depend on the Steiner tree problem. Machine shops, restaurants, etc leave money on the table when their schedules are not well-optimized. I could go on and on.
- affinepplan 3y ago
  yes but theoretical advancements in NP-complete problems very rarely turn into empirical improvements
  - ethanwillis 3y ago
    It's not hard to see why this would be the case when the culture seems to start with the premise of "it's just ivory tower mathematics with no practical consequences" If instead people were willing to set that hubris to the side and treat problems seriously then maybe we would see theoretical advancements be turned into empirical improvements with proper investment. Why would investment be made to operationalize theoretical advancement if the belief is that it's meaningless? The entire reasoning of not treating these problems seriously from the start, then saying they rarely turn into empirical improvements... it all seems very self-fulfilling and circular.
- bjourne 3y ago
  There are polynomial-time approximation schemes for all those problems. Few of the NP-complete problems are both difficult to approximate and have practical use cases. 3SAT is the big exception.
  - klyrs 3y ago
    Steiner tree problems are particularly vexatious in that regard. Polynomial-time approximation only guarantees a solution at most 40% more expensive than optimal. When you're spending tens to hundreds of millions of dollars on an electrical grid, that's quite the differential.
  - CaptainNegative 3y ago
    I don't know which airlines are packing one-dimensional bins :). In dimensions 2 and above, bin packing has no PTAS unless P=NP, and in particular it's hard to derive anything with an approximation ratio appreciably better than sqrt(num_dimensions)). And the famous Steiner tree result holds only in highly structured metrics like the Euclidean plane and some minor generalizations. For general metrics there's a lower bound of around 1.01 unless P=NP.
    - bjourne 3y ago
      Multi-dimensional bin packing in general does not have PTASes. However, for the constrained versions of the problem used in practice, PTASes and other tractable algorithms exist. Same with the STP - very difficult in non-Euclidean space, but all practical applications are in Euclidean spaces.
deleted 3y ago
[deleted]

ackbar03 3y ago

I did a fix on some open source tool that was pretty fancy and had the same operational complexity. But then I realized oh sht, it's now two times slower

CJefferson 3y ago

In my experience of NP-complete research, there tends to be “real world bias”. There are problems we can mostly solve in polynomial time, and those gets lots of study and people talk about them a lot. There are other problems which are equally valid np-complete problems, for example reversing most encryption and hashing algorithms (with hashes you obviously don’t get a unique reversal, but you can get something), which we generally don’t discuss, as they are entirely unsolvable in practice.

bawolff 3y ago
Finding a hash pre-image is kind of an artificial problem, because hash algorithms are specificly chosen to make that hard. I would assume those things are not np-complete and just np.

H8crilA 3y ago

If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. No post-quantum variants, I mean there's nothing at all. Also, if P=NP quantum computers are probably not useful at all, perhaps they're a bit cheaper, that's all. There's a lot of NP-hard problems that you'd love to solve if you could, but you avoid them because you immediately know it's not possible. For example, you could create optimal neural networks that might be 10x? 100x? more powerful for the same size/cost as GPT-4 is. This stuff is likely so beyond the reach of today's knowledge that it would be like talking about quantum mechanics and integrated circuits running at GHz speed to Euclides. It's like when Paul Erdős talked about the Collatz conjecture: "Mathematics may not be ready for such problems."

enriquto 3y ago
> If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. Why do you say that? A problem being in P does not necessarily mean that it's easy, or that it is solvable at all in practice. Recall that the class P contains problems that require a running time of O(n^A(6,6)), where A is the Ackerman function. This is an inconceivably large number, and there's no realistic expectation to solve such a problem for even minuscule values of n, like n=2 or 3. The class P is huge, and our puny linear and quadratic algorithms can only solve its lower, trivial levels. We have not yet started scratching the surface of the enormous set P, yet some of us are arrogant enough to call all of it "easy". For all we know, it may well be that P=NP but have no practical consequences whatsoever.
yeeniee 3y ago
>If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. I don't see how that follows. A polynomial can still have factors or constants on the orders of "not in this universe's lifetime", so for all practical purposes it doesn't matter.

Ar-Curunir 3y ago

Complexity theory doesn't need to have practical applications to be exciting (though it has often led to such practical applications). Complexity theory explores the fundamental nature of computation: what is and isn't feasible. It's a window into how the universe works, and so it's exciting in the same way that, say, general relativity or quantum mechanics is.

chriswarbo 3y ago

> Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics. We need to be careful when distinguishing a "problem" (e.g. SAT) and an "instance of a problem" (e.g. "is this formula satisfiable?"). Heuristics can often help us solve real-world problem instances (e.g. seat planning for this wedding; a Hamiltonian path for this salesman; etc.), at least approximately/close-enough-to-be-useful. However, we must give resource bounds to such implementations (e.g. a timeout), since there's no way to know/check if a given instance will have worst-case behaviour until we run it. What I find fascinating is that we can prove that some problems are just as hard to solve approximately as they are to solve optimally! https://en.wikipedia.org/wiki/Hardness_of_approximation https://en.wikipedia.org/wiki/Hardness_of_approximation