Mučnik Reducibility

In computability theory, a set $P$ of functions $\mathbb \rarr \mathbb$ is said to be Mučnik-reducible to another set $Q$ of functions $\mathbb \rarr \mathbb$ 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 \rarr \mathbb$ 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)

References

Reduction (complexity)

{{mathlogic-stub