Concept in computability theory
In computability theory, a set "P" of functions formula_1 is said to be Mučnik-reducible to another set "Q" of functions formula_1 when for every function "g" in "Q", there exists a function "f" in "P" which is Turing-reducible to "g".
Unlike most reducibility relations in computability, Mučnik reducibility is not defined between functions formula_1 but between sets of such functions. These sets are called "mass problems" and can be viewed as problems with more than one solution. Informally, "P" is Mučnik-reducible to "Q" when any solution of "Q" can be used to compute some solution of "P".