In computability theory, a set P of functions N → N {\displaystyle \mathbb {N} \rightarrow \mathbb {N} } is said to be Medvedev-reducible to another set Q of functions N → N {\displaystyle \mathbb {N} \rightarrow \mathbb {N} } when there exists an oracle Turing machine that 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, that compute functions from P.
See also Mučnik reducibility Turing reducibility Reduction (computability)
References