Glonce

NP-hard doesn't mean unsolvable: these problems get solved in practice

miscThe Glonce editorsHacker News🔥65Glonce rating65Impact55Novelty45Relevance75Surprise60Players18Credibility75

In a post titled 'NP-overrated', published on the personal blog gruhn.me, an unnamed author argues that a lesson many people take from a computer-science education, that NP-hard problems are solvable in theory but hopelessly expensive in practice and that it is basically proven no good algorithms exist, is a myth. The author traces part of the belief to a professor who closed a final lecture with words explicitly flagged as a paraphrase rather than a direct quote: that almost all interesting problems are undecidable, that almost all of the remaining ones are NP-hard, and that together this amounts to 'the final nail in the coffin' for computer science as a project. The author's counter is that the theory is not wrong but is often irrelevant in practice: any algorithm can blow up on some input, yet that does not rule out a fast solution on, in the author's own illustration rather than a measured result, 99.9% of inputs, or on 100% of the inputs that are 'remotely relevant'. The piece frames this gap between theory and practice with a quoted epigraph credited to Benjamin Brewster, who is given no further identification in the text: 'In theory, there is no difference between theory and practice. But in practice, there is.'

The post lists five prominent NP-hard problems and works through each. For dependency resolution in package managers and for type checking, qualified in the piece as applying to 'not all type systems', it argues the theoretical worst case essentially never shows up: both tasks can be slow, but the author says that in their own career they have never seen a 'galactic blow-up'.

Scheduling and the Traveling Salesman Problem, described as technically optimization problems, are said to already have tools that find provably optimal solutions in reasonable time, without falling back to heuristics that give up optimality. The author attributes this to algorithmic progress rather than hardware, noting that algorithmic speedups have outpaced hardware gains over recent decades, and citing an unnamed paper's claim of a 450-billion-fold speedup between 1991 and 2015.

The last example is Boolean satisfiability (SAT), called the archetype of NP-hard problems and said to be routinely solved at scale. The author cites a claim that Amazon solves a billion SMT problems a day; SMT is described in the piece only as 'an even harder version of SAT', and SAT solvers are said to have gotten good enough that SAT is now considered the easy part. On what happens when the worst case does hit, the author's answer mirrors how a stalled network request is handled: add a timeout and show an error message, rather than treating a worst-case blow-up as a reason to avoid an approach altogether.

Key facts

  • The author traces part of the myth to a professor who, in words explicitly flagged as a paraphrase rather than a verbatim quote, called undecidability and NP-hardness together 'the final nail in the coffin' for computer science as a project.
  • For dependency resolution in package managers and for type checking, the author says the theoretical worst case essentially never shows up in their own career, even though both tasks can be slow.
  • Scheduling and the Traveling Salesman Problem already have tools that find provably optimal solutions in reasonable time without falling back to heuristics; a cited but unnamed paper reports a 450-billion-fold algorithmic speedup between 1991 and 2015.
  • Boolean satisfiability (SAT), called the archetype of NP-hard problems, is said to be routinely solved at scale; the piece cites a claim that Amazon solves a billion SMT problems a day and says SAT is now 'the easy part'.
  • For whatever worst case remains, the author's answer mirrors how a stalled HTTP request is already handled: add a timeout and show an error message rather than avoiding the approach altogether.

Why it matters

The post pushes back on a specific, common belief: that once a problem is classified NP-hard, chasing a fast solution is a waste of time. The author says this shows up constantly as a conversation-ending move, quoting people online as saying 'No you can't do it. It's NP-hard. Blah blah', and traces part of its origin to how the subject tends to get taught, closing on a professor's dramatic, self-flagged paraphrase that almost all interesting problems are undecidable, that almost all of the rest are NP-hard, and that together this is 'the final nail in the coffin' for computer science as a project. The counterargument is not that the theory is wrong; worst-case complexity results still hold. It is that worst-case behavior is a poor guide to what happens on the inputs that actually show up, so treating 'NP-hard' as a stop sign for real engineering problems, package management, type systems, scheduling, routing, constraint solving, throws away solutions that already exist and are already in use.

Who it affects

Anyone who studied computer science and came away with the pessimistic framing the post describes, and anyone who invokes NP-hardness to end a discussion about whether a problem is worth attacking. More concretely, the argument touches people building or relying on package managers (dependency resolution), type systems (type checking), schedulers, routing or logistics tools (the Traveling Salesman Problem), and formal methods or constraint-solving tools (SAT and SMT solvers). Amazon is named as one organization running SMT solving at large scale.

How to use it

The post is an argument rather than a product release, but its practical takeaway works like a checklist for reacting to 'that's NP-hard': check whether the worst case actually occurs on the inputs that matter, which the author says it does not, in their own experience, for dependency resolution or type checking; check whether the problem is really an optimization problem where tools already exist that find provably optimal answers in reasonable time, as claimed for scheduling and the Traveling Salesman Problem; and for satisfiability-style problems, treat SAT and SMT solvers as mature, fast tools rather than assuming the theoretical worst case will hit. For whatever worst-case risk remains after that, the author's suggested handling matches how any operation that might hang is already handled elsewhere: set a timeout and show an error message.

How solid is it

This is a first-person blog post making an argument, not a study, and its evidence is mixed in strength. The claim that dependency resolution and type checking avoid worst-case blow-ups rests on the author's own experience, explicitly hedged as 'at least in my career'. The 450-billion-fold algorithmic speedup figure is attributed to a paper the post does not name, so it cannot be checked from the text alone. The claim that Amazon solves a billion SMT problems a day is stated without a source, dataset, or methodology. The 99.9% and 100% figures for how much of the input space a fast algorithm might cover are explicitly the author's own hypothetical illustration, not a measured result. The professor's closing remarks are given only as the author's paraphrase, not a verbatim quote, and neither the professor nor the university or course is named. The author's own name is not given anywhere in the text either; the piece is written in the first person throughout.

Risks and caveats

Read the two headline figures for what they are: the 450-billion-fold speedup comes from a paper the post does not name, and the billion-SMT-problems-a-day claim about Amazon carries no source, dataset, or methodology in the text, so neither can be independently checked from this piece alone. The strongest personal claims, never having seen a 'galactic blow-up' in dependency resolution or type checking, are scoped explicitly to the author's own career ('at least in my career'), not presented as a general guarantee. The piece itself narrows type checking to 'not all type systems,' and it credits no specific algorithm or tool for the 'provably optimal solutions' it describes for scheduling and the Traveling Salesman Problem.

“In theory, there is no difference between theory and practice. But in practice, there is.”

— Benjamin Brewster