# 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 LevinReduction 2013-03-22 13:01:44 2013-03-22 13:01:44 Henry (455) Henry (455) 5 Henry (455) Definition msc 68Q05 msc 68Q10