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	2013-03-22 13:01:44
Last modified on	2013-03-22 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