Note, however, that in order to show that \(\phi \in \sc{VALID}\) requires that we show that \(\phi\) is true with respect to all valuations.  As there exist \(2^n\) valuations for a formula containing \(n \) propositional variables, it is by no means evident that the membership of an arbitrary formula in \(\sc{VALID}\) can be decided in polynomial time by an algorithm which can be implemented as a non-deterministic Turing machine relative to the acceptance and rejection conventions describe above. In fact, the following is another fundamental unresolved question in contemporary complexity theory: