Misplaced Pages

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

1. Hinman, Peter G. (2012). "A survey of Mučnik and Medvedev degrees". Bulletin of Symbolic Logic. 18 (2): 161–229. doi:10.2178/bsl/1333560805. JSTOR 41494559.
2. Simpson, Stephen G. "Mass Problems and Degrees of Unsolvability" (PDF). Retrieved 2024-06-10.

This mathematical logic-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

This article needs additional or more specific categories. Please help out by adding categories to it so that it can be listed with similar articles. (June 2024)

• Theoretical computer science
• Mathematical logic stubs