<p>Standard notions of reduction used in Descriptive Complexity are <a href="https://en.wikipedia.org/wiki/First-order_reduction" rel="noreferrer">first-order reduction</a> and the weaker first-order projection. Definitions of both these notions are found in <a href="https://people.cs.umass.edu/~immerman/book/descriptiveComplexity.html" rel="noreferrer">Immerman's book on Descriptive Complexity</a>. </p>

CC BY-SA 4.0
2019-05-31T08:20:32.850Z
2019-05-31T08:20:32.850Z
Jan Johannsen
<p>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 <span class="math-container">$\mathsf{NP}$</span> using Logics, like e.g. extensions of first-order logic and others (<a href="http://www.ams.org/notices/199510/immerman.pdf" rel="nofollow noreferrer">see here for an introduction</a>). 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?</p>

<lo.logic><reductions><descriptive-complexity>
Reductions in Descriptive Complexity
user3483902
# Reductions in Descriptive Complexity

(Asked by: username_0 on 2019-05-30)

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](http://www.ams.org/notices/199510/immerman.pdf)). 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?

**Tags:** lo.logic, reductions, descriptive-complexity


---

## 1 answers

### Answer by username_1 on 2019-05-31. Score: 7

Standard notions of reduction used in Descriptive Complexity are [first-order reduction](https://en.wikipedia.org/wiki/First-order_reduction) and the weaker first-order projection. Definitions of both these notions are found in [Immerman's book on Descriptive Complexity](https://people.cs.umass.edu/~immerman/book/descriptiveComplexity.html).


---

