Medvedev reducibility

In computability theory, a set P of functions $\mathbb {N} \rightarrow \mathbb {N}$ is said to be Medvedev-reducible to another set Q of functions $\mathbb {N} \rightarrow \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.^[1]

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.^[2]

References

^ Hinman, Peter G. (2012). "A survey of Mučnik and Medvedev degrees". Bulletin of Symbolic Logic. 18 (2): 161–229. doi:10.2178/bsl/1333560805. JSTOR 41494559.
^ Simpson, Stephen G. "Mass Problems and Degrees of Unsolvability" (PDF). Retrieved 2024-06-10.

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

[hinman-1] Hinman, Peter G. (2012). "A survey of Mučnik and Medvedev degrees". Bulletin of Symbolic Logic. 18 (2): 161–229. doi:10.2178/bsl/1333560805. JSTOR 41494559.

[simpson-2] Simpson, Stephen G. "Mass Problems and Degrees of Unsolvability" (PDF). Retrieved 2024-06-10.

[1]

[2]

See also

References