Hacker News Reader

Comment by g42gregory | Hacker News Reader

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.

View on HN

> 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

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.

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.

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."

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

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

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.

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

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.

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.

yes but theoretical advancements in NP-complete problems very rarely turn into empirical improvements

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.

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.

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.

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.

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.

Reply on news.ycombinator.com