> 2. Type checking (not all type systems)
> For (1) and (2), the worst-case just doesn't occur.
I don't think 2. is a good example to be honest, It happens quite a lot. At least it's definitely not in the same category as dependency resolution, where people often don't even know that it's NP-hard.
Typescript, Rust or C++ type system complexity is routinely a compile time problem that people have to work around or tackle from both sides (i.e. either changing the compiler or changing the program).
> Typescript, Rust or C++ type system complexity is routinely a compile time problem that people have to work around or tackle from both sides
True, but this has very little to do with these being NP-hard.
As an example I know well: In Rust, exhaustiveness checking is NP-complete, and trait solving is undecidable. Exhaustiveness checking contributes basically nothing to compile times, and trait solving is significant but that's only because we do it many many times, each particular instance is solved very quickly (and we have limits for how long it can go). Optimizations of both are done using programming tricks and not via algorithmic improvements, almost always.
I think you severely underestimate how much effort goes into tackling the computation complexity of those problems as well. Multiple months (at least) went into tackling various exponential blowups in the next trait solver work. That's a typical symptom for NP-hard problems, there's a consistent stream of exponential cases for which you keep adding various fastpaths and caches for various patterns.
Various crates have explicit workarounds for these issues as well, typically using Box to avoid deep types, e.g. axum's `.route()` added it explicitly to avoid this, I believe.
For match exhaustivness, there's currently an active discussion on it again, because it comes up in derives for big enums, and we just landed an optimization that avoids it for some derive macros.
In other ecosystems, I remember a talk about avoiding exponential blowup for various constructs in C++ templates. Typescript even has a guide for how to write types to avoid complexity problems. With libriaries like `ArkType`, people hit these issues a quite a bit.
I won't claim that this is the majority of the compile time work, but it's something that comes up often enough that I think it's pretty ridiculous to say "the worst-case just doesn't occur."