 Be it still noted that when attention is restricted to finite models, Ronald Fagin’s famous theorem (1974) connects \(\mathbf{ESO}\) and the complexity class \(\mathbf{NP}\): a computational problem is solvable by an algorithm running in non-deterministic polynomial time iff it is definable in \(\mathbf{ESO}\) relative to the class of all finite structures. The following are \(\mathbf{NP}\)-complete properties and hence expressible in \(\mathbf{IFL}\), over the class of all finite models: evenness of the domain, oddness of the domain, 3-colorability of a graph, and the existence of a Hamiltonian path on a  graph.[38] 