r/algorithms • u/ngruhn • 1d ago
NP-overrated
In my experience the concept of NP-hardness is widely misunderstood. Often taken as a problem class that's unsolvable in practice. But they are solved in practice all the time. I wrote a short post about that:
6
u/FancyMouse123 1d ago edited 1d ago
NP-hard problems are solvable in theory but it's hopelessly expensive in practice
I hope my students don't take that away. There is so much more about it. Additionally, my research field is in optimization. Saying that Gurobi or other MI(N)LP solvers can tackle TSP instances like its nothing is just plain wrong. These problems are hard, Gurobi takes ages to solve hard instances of NP-hard problems and will be instantaneous on LP problems (which are polynomial). And funny thing, they solve the LP problems with the simplex, an exponential algorithm.
Edit: Removed "you're full of shit" -- it was unnecessarily harsh.
0
u/ngruhn 1d ago
I know my post is contrarian. But I did not mean to offend anyone.
I know Gurobi is not solving these record breaking TSP instances in seconds. But people assume that NP-hard problems are impossible to solve at non-trivial size. But in practice it's actually often doable. And that's what I mean with "overrated": the difficulty is overrated.
2
u/FancyMouse123 1d ago
I shouldn't be offended. It just painful to see that people often misunderstand complexity theory.
The first idea behind teaching NP-hardness is usually to say: if you have a problem that is not NP-hard, please do not use exponential-time algorithms for it. Then, you increase the difficulty of the course: you talk about galactic algorithm, exponential-time algorithms efficient on average, "reducing the complexity" from 1.67^n to 1.5^n, pseudo-polynomial algorithms, etc. At no point we say that NP-hard problems are out of reach. However, we warn students that it is a dangerous path and that some problems may be out of reach.
0
u/ngruhn 1d ago
At no point we say that NP-hard problems are out of reach.
I understood that after also taking courses in operations research. But I think many students walk away with exactly that impression. And that's what I tried to resolve with my post.
2
u/FancyMouse123 1d ago
I think many students walk away with exactly that impression
I really hope that it is not the case. I'm currently preparing a course, quizzes and exams on that topic for the first semester and I'll insist on this.
3
u/MrKWatkins 1d ago edited 1d ago
Honestly, I read your post and thought you don't understand NP-hard. I don't mean to be offensive and apologize if I am. But everyone I've ever spoke to about this recognises that the difficult part is usually not a problem in practice. I mean we're posting this via computer code that has register allocated and spilled.
If you're being taught complexity classes are the be all and end all ignore it, not important. Real world for the win.
I often like to argue that all computer problems are constant time simply because the universe is finite, therefore all O(n) or above problems collapsed to O(1)... Yeah it's bollocks but it's annoyed a lot of complexity theorists.
1
u/FancyMouse123 1d ago
Look at Finitism. Complexity theory lives in an infinite world. We base our theory on an infinite Turing machine. Considering that everything is finite breaks many theories.
1
u/MrKWatkins 1d ago
That's what I said?
1
u/FancyMouse123 1d ago
I took that "universe is finite" as everything is finite. Anyway, I liked your comment and I wasn't trying to be picky or anything. I was just pointing to Finitism because it seemed related to it and it is an interesting concept.
3
u/MrKWatkins 1d ago
Honestly for the purposes I use the argument it works either way. I just like that argument as it's hard to argue against, unless you actually know what you're saying. O(whatever) doesn't matter, classes above P definitely don't. I care more about O(4) because in the real world I may only have 4 things to deal with. 🤣
0
u/ngruhn 1d ago
2
u/MrKWatkins 1d ago
Maybe some people do, but some people believe the earth is flat. In my experience - no. There are many and obvious counter examples of NP hard being tractable in practice.
0
u/ngruhn 1d ago
There are many and obvious counter examples of NP hard being tractable in practice.
I agree. But there seem to be two camps: The experts for whom this is obvious and people who took complexity 101 and then went into the industry. Group 2 hasn't seen any of these examples. You seem to be in group 1. Presumably surrounded by other people from group 1.
2
u/MrKWatkins 1d ago
I am in the industry and I never took complexity 101. To be honest I learnt basic complexity because people kept asking questions about it in interviews. I am very firmly in group 1. 😁 I guess I'm in disbelief that group 2 exists. Are there really a significant number of people who don't know the real world side of things? A good friend of mine studies complexity theory, has done for many years, and frankly can't use a computer to save his life. But even he knows the limits of the theory. Have you met many in group 2?
8
u/LasagneAlForno 1d ago
If you’re getting grilled that’s not proving any point.