Compiling Rust is NP-hard
...though it's not the flagship borrow checking that's at fault. 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.
Source: Compiling Rust is NP-hard.