First-order reduction
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.
Wikipage disambiguates
Link from a Wikipage to another Wikipage
primaryTopic
First-order reduction
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.
has abstract
In computer science, a first-o ...... other "well-behaved" classes).
@en
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
958,326,942
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
comment
In computer science, a first-o ...... than the logspace reductions.
@en
label
First-order reduction
@en