NP-overrated
Claims that NP-hard problems are “hopelessly intractable” are challenged by examples from package managers, type systems, SAT solvers, and operations research, where real-world instances are routinely solved quickly using heuristics, approximations, or by constraining the problem space. Participants stress that NP-hardness is a worst‑case, asymptotic notion: it proves no algorithm is fast for all inputs, not that practical inputs are unsolvable, and it often guides designers to simplify models or accept “good enough” solutions. At the same time, several comments highlight genuine exponential blow‑ups in tools like Swift, Debian’s aptitude, and regex engines, arguing that understanding complexity theory remains crucial for knowing where those limits lie.
Misunderstandings about NP-hardness
- Several commenters argue many people inaccurately equate “NP-hard” with “hopeless in practice.”
- Others counter that theory is explicit: NP-hard means no polynomial-time algorithm for all inputs is known, not that practical subsets are unsolvable.
- The value of NP-completeness is framed as: it tells you when to stop chasing a general optimal algorithm and instead seek heuristics, special cases, or approximations.
Worst-case vs typical-case behavior
- Many NP-hard problems explode only on rare, carefully constructed instances (e.g., cryptographic constructions, SAT on SHA-256 encodings, some package graphs).
- Real-world instances often have structure (planarity, low treewidth, limited N, domain constraints) that make them tractable.
- “Phase transitions” and pathological corner cases are noted, especially in SAT and constraint problems.
Package managers and dependency resolution
- Formal models show dependency resolution becomes NP-hard when you require single-version constraints and rich negative/version bounds.
- Ecosystems avoid hardness by:
- Dropping uniqueness (npm/yarn with multiple versions).
- Using restricted policies like minimum version selection (Go).
- Allowing limited multiplicity (Cargo) plus heuristics and backstops.
- In practice, most resolutions are fast, but some systems (Debian aptitude, pip, conda) do hit “galactic blow-ups.”
Type systems and type checking
- Some advanced type systems (bidirectional inference, overloading, traits) are NP-hard or undecidable in general.
- Many languages avoid the worst behaviors by design; others (notably Swift, but also C++/Rust/TypeScript in complex cases) exhibit severe compile-time slowdowns.
- Implementers rely on heuristics, cutoffs, and design restrictions rather than solving the full general problem.
Approximation, heuristics, and parameterization
- Approximation algorithms and heuristics are emphasized: TSP, set cover, scheduling, motion planning, integer programming, and timetabling all have good “good-enough” methods.
- Fixed-parameter tractability is highlighted: for some NP-hard problems, running time exponential in a small parameter but polynomial in input size is very effective.
- Operations research, SMT/MIP solvers, and modern SAT solvers are cited as mature technologies that often find exact or near-optimal solutions on large real instances.
Security, regex, and denial of service
- Powerful regex engines can encode NP-hard behavior; catastrophic backtracking is a known DoS vector.
- Timeouts are suggested but controversial; many advocate using regex engines with guaranteed linear-time semantics for untrusted input.