First-order Reduction
   HOME

TheInfoList



Click Here for Items Related To - First-order Reduction
OR:
First-order Reduction on:   [Wikipedia]   [Google]   [Amazon]

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a first-order reduction is a very strong type of reduction between two
computational problem In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computati ...
s in
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
. 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 First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
. Since we have \mbox \subsetneq \mbox, 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 Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
problems are first-order complete as well (Immerman 1999 p. 49-50). For example,
ST-connectivity In computer science, st-connectivity or STCON is a decision problem asking, for vertices ''s'' and ''t'' in a directed graph, if ''t'' is reachability, reachable from ''s''. Formally, the decision problem is given by :. Complexity On a seque ...
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

* Descriptive complexity Reduction (complexity) {{mathlogic-stub