Reducing one problem to another are well known in various settings, such as many-one, randomized, truth-table, logspace or a whole slew of other reductions. Descriptive complexity can alternately characterize problems in $\mathsf{NP}$ using Logics, like e.g. extensions of first-order logic and others (see here for an introduction). So, it is natural to ask how to approach reductions in this context. Are there reductions, based on first-order, or second-order logics used in Descriptive Complexity, or even completeness under these reductions for descriptive complexity?
1 Answer
Standard notions of reduction used in Descriptive Complexity are first-order reduction and the weaker first-order projection. Definitions of both these notions are found in Immerman's book on Descriptive Complexity.