Descriptive complexity begins with the observation that since computational problems are comprised by finite combinatorial objects (e.g. strings, graphs, formulas, etc.), it is possible to describe their instances as finite structures in the conventional sense of first-order model theory. In particular, given a problem \(X\), we associate with each of its instances \(x \in X\) a finite structure \(\mathcal{A}_x\) over a relational signature \(\tau\) whose non-logical vocabulary will depend on the type of objects which comprise \(X\).[45]