Levin reduction
If R1 and R2 are search problems and 𝒞 is a complexity class then a 𝒞 Levin reduction of R1 to R2 consists of three functions g1,g2,g3∈𝒞 which satisfy:
-
•
g1 is a 𝒞 Karp reduction of L(R1) to L(R2)
-
•
If R1(x,y) then R2(f(x),g(x,y))
-
•
If R2(f(x),z) then R1(x,h(x,z))
Note that a 𝒞 Cook reduction can be constructed by calculating f(x), using the oracle to find z, and then calculating h(x,z).
𝒫 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 |