Mučnik reducibility

In computability theory, a set P of functions $\mathbb {N} \rightarrow \mathbb {N}$ is said to be Mučnik-reducible to another set Q of functions $\mathbb {N} \rightarrow \mathbb {N}$ 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 $\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 is Mučnik-reducible to Q when any solution of Q can be used to compute some solution of P.

See also

• Medvedev reducibility
• Turing reducibility
• Reduction (computability)