from Hacker News

Compiling Rust is NP-hard

by NieDzejkob on 7/8/21, 12:41 AM with 1 comments

• by kadoban on 7/8/21, 10:21 AM

  Quite interesting, I had not thought of pattern-exhaustiveness checking like that.

  Isn't compiling several languages, including Rust, actually undecidable though? Seems like if your type system or metaprogramming systems are Turing complete, this has to be the case.

  So that's worse than NP-hard already (though calling it NP-hard is still technically correct).