This correspondence yields a polynomial-time reduction from the complement of SAT to VALID

In contrast to this, there is no a priori guarantee that classes such as \(\textbf{NP}\) defined in terms of non-deterministic models are closed under complementation. For consider a problem such as \(\sc{SAT}\) belonging to this class. \(\overline{\sc{SAT}}\) – i.e. the complement of \(\sc{SAT}\)– consists of the set of formulas for which there does not exist a satisfying valuation – i.e. the contradictory formulas of propositional logic. From this it follows that \(\phi \in \overline{\sc{SAT}}