FO(LFP) is defined purely in terms of logical resources (first-order logic plus a least fixed point operator), not in terms of Turing machines or any specific computational model.

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