A search problem R is 𝒞 self-reducible if there is a 𝒞 Cook reduction of R to L(R). That is, if the decision problemMathworldPlanetmath for L(R) is 𝒞 then so is the search problem for R.

If R is polynomially self-reducible then it is called self-reducible.

Note that L(R) is trivially Cook reducible to R.

Title self-reducible
Canonical name Selfreducible
Date of creation 2013-03-22 13:01:47
Last modified on 2013-03-22 13:01:47
Owner Henry (455)
Last modified by Henry (455)
Numerical id 5
Author Henry (455)
Entry type Definition
Classification msc 68Q05
Classification msc 68Q10