NP is captured by second-order existential logic (SO∃), a characterization that makes no reference to a specific model of computation such as a Turing machine.

4 Descriptive complexity Another connection between logic and computational complexity is provided by the subject known as descriptive complexity theory. As we have seen, a problem \(X\) is taken to be ‘complex’ in the sense of computational complexity theory in proportion to how difficult it is to decide algorithmically. On the other hand, descriptive complexity takes a problem to be ‘complex’ in proportion to the logical resources which are required to describe its instances. In other words, t