It's "only" NP complete if the clauses are known. But here the clauses are expressions, and can have side-effects (ties, threads, overload) so determining whether this would never be true quickly reduces to the halting problem.

And no automaton that's powerful to run Perl on which the halting problem is decideable is known.

Abigail