[Rusky]

I know what NP means, my parenthetical implied that you used it in a way that made no sense.

Undecidable control flow does not inherently make validation undecidable, or NP, or anything else really. The key (like with any sort of type system) is that it's okay to reject some subset of valid programs in exchange for easy enforcement of the invariants you need.