“What I noticed, and would like to share with you today, is that the exhaustiveness checking performed by the Rust compiler on match patterns is a superset of the SAT problem.”
Rust checks that every match covers every case. Encode a boolean formula as match arms and the compiler error hands you the answer. That makes rustc a SAT solver, and SAT is NP-complete. Nobody’s build is slow because of this. It’s slow for plenty of other reasons.