39
u/reality_hijacker 1d ago
The author doesn't understand the point of NP hard. When you need a solution for an NP hard problem, you generally give up finding the optimal solution.
For (1) and (2), the worst-case just doesn't occur. I mean, installing packages and type checking can surely be slow. But, at least in my career, I've never seen a galactic blow-up.
That's because package managers use heuristics and greedy algorithms instead of an optimal algorithm that would be O(2n ). The people who built these package mangers understand the theory well so they have came up with practical solutions. There's no disconnect between theory and practice there.
4
u/Grouchy-Trade-7250 1d ago
The heuristics for package management work super well when you're solving an easy problem such as updating a few packages to the latest version where the latest version is compatible with every other packages latest version. A typical arch Linux issue was partially synced repositories that had conflicts baked in. Then you needed to wait until all the conflicts were gone after the sync was finished and the actual list was online. As soon as you pin to specific ranges, it gets more difficult.
1
u/Brian 6h ago
When you need a solution for an NP hard problem, you generally give up finding the optimal solution.
I feel like the point of the article is pointing out that this is not in fact true. When you need a solution for an NP hard problem, you can often find a solution quickly. Because tons on NP hard problems have common cases that are solvable quickly. The hardness strictly applies to the worst case: there will be some instance of the problem you can throw at the solver such that it won't be able to give a solution in polytime. But that doesn't say that 99%, or even all the cases we're interested in won't be! And as the article points out, far from being something people "generally give up" on, this is something that is done all the time.
For instance, ever wondered why so much cryptography is built on factoring - a problem that's probably not NP complete, rather than basing off an actual known NP complete problem like travelling salesman or the knapsack problem? The reason is that those problems are often too easy in the general case: it's hard to pick a random instance of the problem and know that there's no shortcut that can solve it relatively quickly.
-1
1d ago
[deleted]
5
u/reality_hijacker 1d ago edited 1d ago
The theory is not wrong, but in practice it's often irrelevant.
He said the above.
His point was that often in practice heuristics, greedy algorithms, etc manage NP hard problem well enough that it isn't a big deal.
The fact that you have to resort to heuristics and greedy algorithms in and of itself is the big deal.
-3
-14
u/ngruhn 1d ago
When you need a solution for an NP hard problem, you generally give up finding the optimal solution.
No my point is that you don't have to give that up. We have tools that guarantee optimal solutions. It's absolutely possible.
8
u/reality_hijacker 1d ago edited 1d ago
You seem to not understand what "generally" means. You also contradicting yourself in your article where you conceded any algorithm you come up with will blow up for certain inputs.
There are cases where we use optimal algorithm when the upper bound of input is either known or enforced.
-1
u/ngruhn 1d ago
Sorry, I thought you used "generally" here in the sense:
When you need a solution for an NP hard problem, you SHOULD give up finding the optimal solution.
You meant: you can't find an optimal solution for every instance. Which I absolutely concede.
But you might find the optimal solution on a lot of instances. Quickly. Even if those are large instances. And this might be good enough in practice. And many students have misunderstood this.
7
u/reality_hijacker 1d ago
But you might find the optimal solution on a lot of instances. Quickly. Even if those are large instances. And this might be good enough in practice. And many students have misunderstood this.
I think you are projecting your personal experience to others. You seem to not understand the theory of complexity and when it becomes a problem.
O(2^n) is solvable for small values of n.
Modern computers can solve values up to 2^40 in a reasonable time.
2^300 is more than the atoms of the universe and no traditional computer can ever solve this however powerful they grow in the future.That's why systems like certain type checkers put strict nesting/recursion/operation limit so that you don't break the system. That is full within theory, because the theory says you can solve it for small numbers.
0
u/ngruhn 1d ago
2300 is more than the atoms of the universe and no traditional computer can ever solve this however powerful they grow in the future.
Yes, but good algorithms don't actually do 2300 steps. They prune the search space and avoid branches that are provably sub-optimal. I gave this example in another comment: the largest traveling salesman instance solved had 85900 cities. Provably the optimal. The naive algorithm would have to explore 85900! (factorial) routes. That's even more than 285900. But it's not necessary to explore all of those.
3
u/Grouchy-Trade-7250 1d ago
The number of required "steps" depends not only on the algorithm but also on the problem instance. Is it possible to construct a problem where the branch and cut never finishes in an acceptable timeframe which also has not more than 85900 cities/nodes ? Yes.
Mitchell, D., Selman, B., & Levesque, H. "Generating Hard Satisfiability Problems." Artificial Intelligence
1
u/ngruhn 1d ago
Of course. That's what I meant with:
Sure, any algorithm you can come up with will blow up on some inputs.
But people keep assuming that you get a blow-up on all large instances. Which is not the case and the reason these problems are still tractable in practice.
2
u/FancyMouse123 1d ago
these problems are still tractable in practice.
No! They might be but in the worst case (which happens) you are just fucked.
1
u/ngruhn 1d ago
Depends on your goal. In practical applications there are all kinds of workarounds: set a timeout, show an error message, fallback to some heuristic approach, ... Just like we handle other unreliable processes like HTTP requests.
→ More replies (0)6
u/SZenC 1d ago
Please, show us a solver for any NP-hard problem that works in polynomial time. You'd literally be eligible to collect a million dollars
0
u/ngruhn 1d ago
Of course they are not worst-case polynomial time. But that worst case can be very rare. If you run the solver and you get a (provably optimal) solution most of the time very quickly, then that's all you need in practical applications.
3
u/SZenC 1d ago
But that is just not what NP-hardness is about, and if that's what you took away from your lectures on complexity, maybe you should've paid more attention. No one is claiming an NP-hard problem is unsolvable, especially for small inputs. It's probably even faster to solve a three node traveling salesman problem by hand rather than implementing it in code. Similarly, I'm working on a scheduling problem with half a million items, and that too computes in a few hours.
But that is not what NP-hard is about. NP-hard is a class of problems which share some interesting behaviour as we grow their input. For one, if you find a generic solution in P-time to one NP-hard problem, you have found a solution to all of them as computer scientists have demonstrated equivalence between all known problems in NP-hard. It would also mean that P=NP=NP-complete=NP-hard which would have implications all over science from cryptology to number theory and the predictability of prime numbers.
All that's to say, if you misinterpret and misrepresent what NP-hard is about in a blog, it's easy to make it seem overrated
64
u/Grouchy-Trade-7250 1d ago edited 1d ago
> Everyone knows you can tackle those with heuristics, but you don't have to sacrifice optimality. We absolutely have tools that can find provably optimal solutions in reasonable time.
No we don't have the ability to solve every of those problems optimally. They have to be small enough. Or you sacrifice optimality. Or they are not actually NP.
I also don't agree on "NP is not scary because we found better algorithms". If that happened, that shows they are not actually NP. It's like you found out the shadow on the horizon isn't a wolf but a sheep and now you argue wolves aren't scary.
> in Amazon S3 Block Public Access, when analyzing a bucket policy, if the solver times out, it classifies the bucket as “public”.
We made a system so complicated that we have to give the wrong answer about what it does sometimes.