Jump to content

Mučnik reducibility

From Wikipedia, the free encyclopedia

In computability theory, a set P of functions is said to be Mučnik-reducible to another set Q of functions when for every function g in Q, there exists a function f in P which is Turing-reducible to g.[1]

Unlike most reducibility relations in computability, Mučnik reducibility is not defined between functions 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.[2]

See also

[edit]

References

[edit]
  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.