Descriptive characterizations have been obtained for many of the major complexity classes considered in Section 3, several of which are summarized in Table 2. The first such characterization was established with respect to second-order existential logic (\(\mathsf{SO}\exists\)). The language of this system includes formulas of the form \(\exists Z_1 \ldots \exists Z_n \phi(\vec{x},Z_1,\ldots,Z_n)\) where the variables \(Z_i\) are second-order and \(\phi\) itself contains no other second-order quantifiers. Fagin (1974) established the following: