Content deleted Content added
m Proposed merge: https://en.wikipedia.org/wiki/Talk:Reduction_(complexity)#Untitled Tags: Reverted Visual edit |
Link suggestions feature: 1 link added. |
||
| (6 intermediate revisions by 6 users not shown) | |||
Line 1:
{{other uses|Reduction (disambiguation)
In [[computability theory]], many '''reducibility relations''' (also called '''reductions''', '''reducibilities''', and '''notions of reducibility''') are studied. They are motivated by the question: given sets <math>A</math> and <math>B</math> of natural numbers, is it possible to effectively convert a method for deciding membership in <math>B</math> into a method for deciding membership in <math>A</math>? If the answer to this question is affirmative then <math>A</math> is said to be '''reducible to''' <math>B</math>.
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 58 ⟶ 59:
*E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", ''Bulletin of the American Mathematical Society'', volume 50, pages 284–316.
* 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 ==
*[https://plato.stanford.edu/entries/recursive-functions/ Stanford Encyclopedia of Philosophy: Recursive Functions]
[[Category:Reduction (complexity)| ]]
| |||