Reduction (computability theory): Difference between revisions

Revision as of 02:33, 26 February 2007

Revision as of 02:38, 26 February 2007

Line 1:

In [[computability theory]], many '''reducibility relations''' (also called '''reductions''', '''reducibilities''', and '''notions of reducibility''') are studied. They are motivated by the question: given sets ''A'' and ''B'' of natural numbers, is it possible to effectively convert a method for deciding membership in ''B'' into a method for deciding membership in ''A''? If the answer to this question is affirmative then ''A'' is said to be '''reducible to ''B' ''B''. The study of reducibility notions is motivated by the study of [[decision problems]].

The study of reducibility notions is motivated by the study of [[decision problems]]. For many notions of reducibility, if any [[computable set|noncomputable]] set is reducible to a set ''A'' then ''A'' must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable.

== Reducibility relations==