# 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 |
---|---|

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 |