The Medvedev and Muchnik degrees

Paul Shafer, University of Leeds. Part of the proof, constructions and computing seminar series.

This talk is an introduction to the Medvedev and Muchnik degrees. Informally, let P and Q represent two mathematical problems. We say that P reduces to Q if every solution to Q can be used to find a solution to P. Medvedev reducibility and Muchnik reducibility are analogs of Turing reducibility that formalize this notion. We identify problems P and Q with their respective sets of solutions (coded as sets of functions) and say that P reduces to Q if every member (i.e., solution) of Q computes some member (i.e., solution) of P. Medvedev and Muchnik introduced their reducibilities and corresponding degree structures to formalize Kolmogorov's ideas for a "calculus of problems" and a "logic of problem solving."

The hope was that the Medvedev and Muchnik degrees would give computational semantics for intuitionistic logic, but it turns out that they give semantics for an intermediate logic called "weak excluded middle" (and also called "Jankov's logic"). We discuss the basic structure of the Medvedev and Muchnik degrees, the above connections to intermediate logics, and also definability and complexity results.

Paul Shafer, University of Leeds