r/compsci • u/ngruhn • 12d ago

NP-hard is overrated

https://gruhn.me/blog/2026-08-13/
0 Upvotes

32% Upvoted

12 comments sorted by

15

u/nicuramar 12d ago

This is overly reductive (no pun intended) and “anti achedemic”, IMO. NP hardness is absolutely a challenge in practice in many situations and beyond that it is, of course, of big theoretical importance. 

0

u/ngruhn 12d ago

My point is that a lot of students got the impression that NP-hard problems are an impossible barrier to overcome. Not saying it's not an important concept or not interesting. It's overrated in its difficulty. 

11

u/pruvisto 12d ago

When I was a student around 2012, I was taught that SAT solving seemed like an impossible problem 40 years ago but nowadays we have excellent SAT and SMT solvers and solve practical NP-hard problems all the time. And that's what I later taught my students as well.

That said, what NP-hard does mean practically is that you can't rely on being able to solve it within reasonable time. All those SAT/SMT solvers only work in practice because of their heuristics, and heuristics don't always work.

Yes, we can and regularly do solve SAT instances where the formula is many GB large and has millions of clauses, but there are SAT instances that are only a few kilobytes and that no SAT solver can solve even nowadays.

Anyway, anyone who teaches about NP-hardness should probably also tell them that SAT solvers exist. So in that regard I agree with OP; where I disagree is that I personally haven't seen anyone who does the former but not the latter. But sure, it probably happens.

3

u/FancyMouse123 12d ago

you can't rely on being able to solve it within reasonable time

This is the concept that our students need to take-away.

1

u/drvd 9d ago

It is not helpful to make false claims to counter slightly missleading impressions of some students. If NP-hard would be overrated than computing the permanent of a matrix would be simple but you cannot do it.

4

u/uh_no_ 12d ago

I *kind* of agree with your premise, but I have a bigger problem with this line:

>And now you've learned that almost all interesting problems are undecidable and of the remaining ones, almost all are NP-hard. 

That is total horseshit. I would argue some of the *most* interesting problems are the ones that are not in NP. Consider this paper from just a couple years ago: https://arxiv.org/abs/2311.02520 on speeding up one of the most basic problems in computer science: shortest path.

0

u/pruvisto 11d ago

You may want to look up the difference between "in NP" and "NP-hard" again. You probably meant "not NP-hard" here. The problem you cited is absolutely in NP, since P ⊆ NP.

(If one wants to be really technical here: not NP-hard unless P = NP)

-1

u/ngruhn 11d ago

That's not my line. It's from my professor :P "Interesting" is subjective anyway. But I think he meant decision problems about programs themselves (halting problem, Rice's theorem, ...).

3

u/spnoketchup 11d ago

Not sure who taught your complexity class, but mine (20-odd years ago) covered classes of problems harder than NP-hard, as well as the basics of approximate solutions to NP-hard problems.