5
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.