# self-reducible

A search problem $R$ is $\mathcal{C}$ self-reducible if there is a $\mathcal{C}$ Cook reduction of $R$ to $L(R)$. That is, if the decision problem for $L(R)$ is $\mathcal{C}$ 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 Selfreducible 2013-03-22 13:01:47 2013-03-22 13:01:47 Henry (455) Henry (455) 5 Henry (455) Definition msc 68Q05 msc 68Q10