NP-overrated
Points and comments are a snapshot, not live.
NP-hard problems are often tractable in practice despite their theoretical worst-case complexity.
The author argues that NP-hardness is frequently misunderstood as meaning problems are intractable in practice. While any algorithm will blow up on some inputs, fast solutions exist for 99.9% of cases or all relevant inputs. Examples include dependency resolution, type checking, scheduling, and traveling salesman, which can be solved optimally via modern tools. SAT, the archetypical NP-hard problem, is routinely solved at scale-Amazon processes a billion SMT queries daily. Algorithmic speedups have outpaced hardware gains, with a cited 450-billion-fold improvement between 1991 and 2015.
What commenters are saying
Commenters broadly agree, but emphasize that practical solutions require limiting the problem space or simplifying constraints. One notes package managers like NPM drop version uniqueness, making resolution not NP-hard, while Cargo and Go also restrict cases. Others highlight the phase transition property of NP-hard problems: worst-case instances are rare in practice, but cryptography deliberately constructs such edge cases. Another points out that clever pre-passes and array-based linear scans often beat complex O(logn) algorithms on modern hardware due to memory access patterns.