Mučnik reducibility

In computability theory, a set ${\displaystyle P}$ of functions ${\displaystyle \mathbb {N} \rightarrow \mathbb {N} }$ is said to be Mučnik-reducible to another set ${\displaystyle Q}$ of functions ${\displaystyle \mathbb {N} \rightarrow \mathbb {N} }$ when for every function ${\displaystyle g}$ in ${\displaystyle Q}$, there exists a function ${\displaystyle f}$ in ${\displaystyle P}$ which is Turing-reducible to ${\displaystyle g}$.^[1]

Unlike most reducibility relations in computability, Mučnik reducibility is not defined between functions ${\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, ${\displaystyle P}$ is Mučnik-reducible to ${\displaystyle Q}$ when any solution of ${\displaystyle Q}$ can be used to compute some solution of ${\displaystyle P}$.^[2]

See also

• Medvedev reducibility
• Turing reducibility
• Reduction (computability)