This article needs attention from an expert in Mathematics. Please add a reason or a talk parameter to this template to explain the issue with the article. (December 2024) |
In computability theory, a set of functions is said to be Medvedev-reducible to another set of functions when there exists an oracle Turing machine that computes some function in whenever it is given some function from as an oracle.
Medvedev reducibility is a uniform variant of Mučnik reducibility, requiring a single oracle machine that can compute some function of given any oracle from , instead of a family of oracle machines, one per oracle from , that compute functions from .