Levin reduction
If ${R}_{1}$ and ${R}_{2}$ are search problems and $\mathcal{C}$ is a complexity class^{} then a $\mathcal{C}$ Levin reduction of ${R}_{1}$ to ${R}_{2}$ consists of three functions ${g}_{1},{g}_{2},{g}_{3}\in \mathcal{C}$ which satisfy:

•
${g}_{1}$ is a $\mathcal{C}$ Karp reduction of $L({R}_{1})$ to $L({R}_{2})$

•
If ${R}_{1}(x,y)$ then ${R}_{2}(f(x),g(x,y))$

•
If ${R}_{2}(f(x),z)$ then ${R}_{1}(x,h(x,z))$
Note that a $\mathcal{C}$ Cook reduction can be constructed by calculating $f(x)$, using the oracle to find $z$, and then calculating $h(x,z)$.
$\mathcal{P}$ Levin reductions are just called Levin reductions.
Title  Levin reduction 

Canonical name  LevinReduction 
Date of creation  20130322 13:01:44 
Last modified on  20130322 13:01:44 
Owner  Henry (455) 
Last modified by  Henry (455) 
Numerical id  5 
Author  Henry (455) 
Entry type  Definition 
Classification  msc 68Q05 
Classification  msc 68Q10 