Matches in DBpedia 2014 for { <http://dbpedia.org/resource/First-order_reduction> ?p ?o. }
Showing items 1 to 12 of
12
with 100 items per page.
- First-order_reduction abstract "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).".
- First-order_reduction wikiPageID "7908748".
- First-order_reduction wikiPageRevisionID "571822609".
- First-order_reduction hasPhotoCollection First-order_reduction.
- First-order_reduction subject Category:Descriptive_complexity.
- First-order_reduction comment "In computer science, a first-order reduction is a very weak type of reduction between two computational problems in computational complexity theory.".
- First-order_reduction label "First-order reduction".
- First-order_reduction sameAs m.026jnj7.
- First-order_reduction sameAs Q5452200.
- First-order_reduction sameAs Q5452200.
- First-order_reduction wasDerivedFrom First-order_reduction?oldid=571822609.
- First-order_reduction isPrimaryTopicOf First-order_reduction.