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.

单词	LevinReduction
释义	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.
随便看	WeakHomotopyEquivalence weak homotopy equivalence WeakHopfAlgebra weak Hopf algebra WeakHopfCalgebra weak Hopf C-algebra WeaklyCompactCardinal weakly compact cardinal WeaklyCompactCardinalsAndTheTreeProperty weakly compact cardinals and the tree property WeaklyCountablyCompact weakly countably compact WeaklyHolomorphic weakly holomorphic WeakPrime weak prime WeakTopology weak- topology WeakTopologyOfTheSpaceOfRadonMeasures weak-* topology of the space of Radon measures WedderburnArtinTheorem Wedderburn-Artin theorem WedderburnEtheringtonNumber Wedderburn-Etherington number WedderburnsTheorem