In computability theory, a set P {\displaystyle P} of functions N → N {\displaystyle \mathbb {N} \rightarrow \mathbb {N} } is said to be Mučnik-reducible to another set Q {\displaystyle Q} of functions N → N {\displaystyle \mathbb {N} \rightarrow \mathbb {N} } when for every function g {\displaystyle g} in Q {\displaystyle Q} , there exists a function f {\displaystyle f} in P {\displaystyle P} that is Turing-reducible to g {\displaystyle g} . Unlike most reducibility relations in computability, Mučnik reducibility is not defined between functions N → N {\displaystyle \mathbb {N} \rightarrow \mathbb {N} } 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 {\displaystyle P} is Mučnik-reducible to Q {\displaystyle Q} when any solution of Q {\displaystyle Q} can be used to compute some solution of P {\displaystyle P} .
See also Medvedev reducibility Turing reducibility Reduction (computability)
References