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.
随便看	p-adic cyclotomic character PadicExponentialAndPadicLogarithm p-adic exponential and p-adic logarithm PadicIntegers p-adic integers PadicRegulator p-adic regulator PadicValuation p-adic valuation PadovanSequence Padovan sequence PairingFunction pairing function PairwiseComaximalIdealsProperty pairwise comaximal ideals property PairwiseDisjoint pairwise disjoint PaleyWienerTheorem Paley-Wiener theorem Palindrome palindrome PalindromicNumber palindromic number PalindromicPrime palindromic prime