Jump to content

First-order reduction

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Mark viking (talk | contribs) at 19:53, 6 September 2013 (Added context to first sentence). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a first-order reduction is a very weak type of reduction between two computational problems in computational complexity theory. A first-order reduction is a reduction where each component is restricted to be in the class FO of problems calculable in first-order logic.

Since we have , the first-order reductions are weaker reductions than the logspace reductions.

Many important complexity classes are closed under first-order reductions, and many of the traditional complete problems are first-order complete as well (Immerman 1999 p. 49-50). For example, ST-connectivity is FO-complete for NL, and NL is closed under FO reductions (Immerman 1999, p. 51) (as are P, NP, and most other "well-behaved" classes).

References

  • Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6.