title: First-order reduction
text: # First-order reduction
  
  In computer science, a first-order reduction is a very strong 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 stronger 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).
  
  