About: First-order reduction

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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 , the first-order reductions are stronger reductions than the logspace reductions.

Property Value
dbo:abstract
  • 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 , 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). (en)
dbo:wikiPageID
  • 7908748 (xsd:integer)
dbo:wikiPageLength
  • 1334 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1055368138 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • 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 , the first-order reductions are stronger reductions than the logspace reductions. (en)
rdfs:label
  • First-order reduction (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License