In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, a set ''P'' of functions
is said to be Medvedev-reducible to another set ''Q'' of functions
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
In computability theory, a set P of functions \mathbb \rarr \mathbb is said to be Mučnik-reducible to another set Q of functions \mathbb \rarr \mathbb when for every function g in Q, there exists a function f in P which is Turing-reducible to g.
...
, 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
In computability theory, a set P of functions \mathbb \rarr \mathbb is said to be Mučnik-reducible to another set Q of functions \mathbb \rarr \mathbb when for every function g in Q, there exists a function f in P which is Turing-reducible to g.
...
*
Turing reducibility
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm ...
*
Reduction (computability)
References
[
]
[
]
Theoretical computer science
Reduction (complexity)
Computability theory
{{mathlogic-stub