Reduction (computability theory): Difference between revisions

Revision as of 12:36, 1 July 2022

Latest revision as of 17:20, 6 July 2025

(3 intermediate revisions by 3 users not shown)

Line 5:

== Reducibility relations==

A '''reducibility relation''' is a [[binary relation]] on sets of natural numbers that is

* [[Reflexive relation|Reflexive]]: Every set is reducible to itself.

* [[transitive relation|Transitive]]: If a set <math>A</math> is reducible to a set <math>B</math> and <math>B</math> is reducible to a set <math>C</math> then <math>A</math> is reducible to <math>C</math>.

Line 53:

== References ==

{{refbegin}}

* K. Ambos-Spies and P. Fejer, 2006. "[http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf Degrees of Unsolvability]." Unpublished preprint.

* P. Odifreddi, 1989. ''Classical Recursion Theory'', North-Holland. {{isbn|0-444-87295-7}}

Line 59 ⟶ 60:

* H. Rogers, Jr., 1967. ''The Theory of Recursive Functions and Effective Computability'', second edition 1987, MIT Press. {{isbn|0-262-68052-1}} (paperback), {{isbn|0-07-053522-1}}

* G. Sacks, 1990. ''Higher Recursion Theory'', Springer-Verlag. {{isbn|3-540-19305-7}}

{{refend}}

== External links ==

[[Category:Reduction (complexity)| ]]

== Internet Resources ==

*[https://plato.stanford.edu/entries/recursive-functions/ Stanford Encyclopedia of Philosophy: Recursive Functions]

[[Category:Reduction (complexity)| ]]