Medvedev reducibility

Template:Short description Template:Expert needed In computability theory, a set P of functions $\mathbb{N}\to \mathbb{N}$ is said to be Medvedev-reducible to another set Q of functions $\mathbb{N}\to \mathbb{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.Template:R

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.Template:R

See also

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