Levin reduction

If R1 and R2 are search problems and 𝒞 is a complexity classPlanetmathPlanetmath 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