Medvedev reducibility explained

In computability theory, a set P of functions

N \rarr N is said to be Medvedev-reducible to another set Q of functions N \rarr N when there exists an oracle Turing machine which computes some function of P whenever it is given some function from Q as an oracle.

Medvedev reducibility is a uniform variant of Mučnik reducibility, requiring a single oracle machine that can compute some function of P given any oracle from Q, instead of a family of oracle machines, one per oracle from Q, which compute functions from P.

See also

• Mučnik reducibility
• Turing reducibility
• Reduction (computability)

References

^{[1] [2]}

Notes and References

1. Hinman . Peter G. . A survey of Mučnik and Medvedev degrees . Bulletin of Symbolic Logic . 2012 . 18 . 2 . 161–229 . 10.2178/bsl/1333560805 . 41494559 .
2. Web site: Simpson . Stephen G. . Mass Problems and Degrees of Unsolvability . 2024-06-10 .