"Na Teoria da computa\u00E7\u00E3o, muitos tipos de redu\u00E7\u00F5es s\u00E3o estudadas. A motiva\u00E7\u00E3o para tal, \u00E9 a seguinte: dado os conjuntos de n\u00FAmeros naturais A e B, \u00E9 poss\u00EDvel efetivamente converter um m\u00E9todo de decis\u00E3o para B em um m\u00E9todo de decis\u00E3o para A? Se a resposta para essa quest\u00E3o for positiva, ent\u00E3o pode se dizer que A \u00E9 redut\u00EDvel a B."@pt . . . . . . . . . "In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets and of natural numbers, is it possible to effectively convert a method for deciding membership in into a method for deciding membership in ? If the answer to this question is affirmative then is said to be reducible to ."@en . . . . . . . "Reduction (computability theory)"@en . "Na Teoria da computa\u00E7\u00E3o, muitos tipos de redu\u00E7\u00F5es s\u00E3o estudadas. A motiva\u00E7\u00E3o para tal, \u00E9 a seguinte: dado os conjuntos de n\u00FAmeros naturais A e B, \u00E9 poss\u00EDvel efetivamente converter um m\u00E9todo de decis\u00E3o para B em um m\u00E9todo de decis\u00E3o para A? Se a resposta para essa quest\u00E3o for positiva, ent\u00E3o pode se dizer que A \u00E9 redut\u00EDvel a B. O estudo de no\u00E7\u00F5es de redutibilidade \u00E9 motivado pelo estudo da decis\u00E3o de problemas. Para no\u00E7\u00E3o de muitos problemas de redutibilidade, se algum conjunto n\u00E3o-comput\u00E1vel \u00E9 redut\u00EDvel a um conjunto A, ent\u00E3o A deve ser n\u00E3o comput\u00E1vel. Isto nos d\u00E1 uma t\u00E9cnica muito poderosa para provar que muitos conjuntos de problemas s\u00E3o n\u00E3o-comput\u00E1veis."@pt . . "12796"^^ . . . . . . "1119788903"^^ . . . . . "Redu\u00E7\u00E3o (teoria da recurs\u00E3o)"@pt . "In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets and of natural numbers, is it possible to effectively convert a method for deciding membership in into a method for deciding membership in ? If the answer to this question is affirmative then is said to be reducible to . The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set then must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable."@en . . "9719800"^^ . . . . . . . . . . . . . . . . . . . .