Misplaced Pages

Medvedev reducibility

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Concept in computability theory
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. WikiProject Mathematics may be able to help recruit an expert. (December 2024)

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 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, 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

References

  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.
  2. Simpson, Stephen G. "Mass Problems and Degrees of Unsolvability" (PDF). Retrieved 2024-06-10.
Stub icon

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

Categories: