NP can be characterized by the logic SO∃ without reference to any specific model of computation such as a Turing machine or alternating machine.

In other words, the descriptive complexity of \(X\) is measured according to the sort of formulas which is needed to define its instances relative to an appropriate background class of finitary structures. g. ), it is possible to describe their instances as finite structures in the conventional sense of first-order model theory. [45] Given such a signature \(\tau\), we define \(\text{Mod}(\tau)\) to be the class of all \(\tau\)-structures with finite domain. In the context of descriptive complex