self-reducible

A search problem $R$ is $𝒞$ self-reducible if there is a $𝒞$ Cook reduction of $R$ to $L(R)$. That is, if the decision problem 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