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.