First-order reduction

First-order reduction

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 mbox{FO} subsetneq mbox{L}, 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

*cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | id = ISBN 0-387-98600-6


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Reduction of order — is a technique in mathematics for solving second order ordinary differential equations. It is employed when one solution y 1(x) is known and a second linearly independent solution y 2(x) is desired.A Simple ExampleConsider the general second… …   Wikipedia

  • Order of Saint Augustine — Abbreviation OSA Formation March, 1256 Type Catholic religious ord …   Wikipedia

  • Reduction — Re*duc tion (r[ e]*d[u^]k sh[u^]n), n. [F. r[ e]duction, L. reductio. See {Reduce}.] 1. The act of reducing, or state of being reduced; conversion to a given state or condition; diminution; conquest; as, the reduction of a body to powder; the… …   The Collaborative International Dictionary of English

  • Reduction ascending — Reduction Re*duc tion (r[ e]*d[u^]k sh[u^]n), n. [F. r[ e]duction, L. reductio. See {Reduce}.] 1. The act of reducing, or state of being reduced; conversion to a given state or condition; diminution; conquest; as, the reduction of a body to… …   The Collaborative International Dictionary of English

  • Reduction descending — Reduction Re*duc tion (r[ e]*d[u^]k sh[u^]n), n. [F. r[ e]duction, L. reductio. See {Reduce}.] 1. The act of reducing, or state of being reduced; conversion to a given state or condition; diminution; conquest; as, the reduction of a body to… …   The Collaborative International Dictionary of English

  • First baseman — First base, or 1B , is the first of four stations on a baseball diamond which must be touched in succession by a baserunner in order to score a run for that player s team. A first baseman is the player on the team playing defense who fields the… …   Wikipedia

  • Order of Ouissam Alaouite — / Royal Order of Al Alaoui Order of Ouissam Alaouite Grand Order Awarded by The King of …   Wikipedia

  • First Stadtholderless Period — The First Stadtholderless Period or Era (1650 1672) (Dutch Eerste Stadhouderloze Tijdperk ) is the period in the history of the Dutch Republic in which it reached the zenith of its economic, military and political Golden Age. The term has… …   Wikipedia

  • Order of integration (calculus) — For the summary statistic in time series, see Order of integration. Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus  Derivative Change of variables Implicit differentiati …   Wikipedia

  • order — 1) In business and trade, making a request to deliver, sell, receive, or purchase goods or services; 2) In the securities and futures trade, instructions to a broker on how to buy or sell. The most common orders in futures markets are market… …   Financial and business terms

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”