Mučnik reducibility

Template:Short description In computability theory, a set $P$ of functions $\mathbb{N}\to \mathbb{N}$ is said to be Mučnik-reducible to another set $Q$ of functions $\mathbb{N}\to \mathbb{N}$ when for every function $g$ in $Q$, there exists a function $f$ in $P$ which is Turing-reducible to $g$.Template:R

Unlike most reducibility relations in computability, Mučnik reducibility is not defined between functions $\mathbb{N}\to \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$.Template:R

See also

• Medvedev reducibility
• Turing reducibility
• Reduction (computability)