# Cook reduction

Given two (search or decision) problems ${\mathrm{{\rm O}\x80}}_{1}$ and ${\mathrm{{\rm O}\x80}}_{2}$ and a complexity class^{} $\mathrm{\pi \x9d\x92\x9e}$, a $\mathrm{\pi \x9d\x92\x9e}$ *Cook reduction* of ${\mathrm{{\rm O}\x80}}_{1}$ to ${\mathrm{{\rm O}\x80}}_{2}$ is a Turing machine^{} appropriate for $\mathrm{\pi \x9d\x92\x9e}$ which solves ${\mathrm{{\rm O}\x80}}_{1}$ using ${\mathrm{{\rm O}\x80}}_{2}$ as an oracle (the Cook reduction itself is not in $\mathrm{\pi \x9d\x92\x9e}$, since it is a Turing machine, not a problem, but it should be the class of bounded Turing machines corresponding to $\mathrm{\pi \x9d\x92\x9e}$). The most common type are $\mathrm{\pi \x9d\x92\xab}$ Cook reductions, which are often just called Cook reductions.

If a Cook reduction exists then ${\mathrm{{\rm O}\x80}}_{2}$ is in some sense βat least as hardβ as ${\mathrm{{\rm O}\x80}}_{1}$, since a machine which solves ${\mathrm{{\rm O}\x80}}_{2}$ could be used to construct one which solves ${\mathrm{{\rm O}\x80}}_{1}$. When $\mathrm{\pi \x9d\x92\x9e}$ is closed under appropriate operations, if ${\mathrm{{\rm O}\x80}}_{2}\beta \x88\x88\mathrm{\pi \x9d\x92\x9e}$ and ${\mathrm{{\rm O}\x80}}_{1}$ is $\mathrm{\pi \x9d\x92\x9e}$-Cook reducible to ${\mathrm{{\rm O}\x80}}_{2}$ then ${\mathrm{{\rm O}\x80}}_{1}\beta \x88\x88\mathrm{\pi \x9d\x92\x9e}$.

A $\mathrm{\pi \x9d\x92\x9e}$ *Karp reduction* is a special kind of $\mathrm{\pi \x9d\x92\x9e}$ Cook reduction for decision problems^{} ${L}_{1}$ and ${L}_{2}$. It is a function $g\beta \x88\x88\mathrm{\pi \x9d\x92\x9e}$ such that:

$$x\beta \x88\x88{L}_{1}\beta \x86\x94g\beta \x81\u2019(x)\beta \x88\x88{L}_{2}$$ |

Again, $\mathrm{\pi \x9d\x92\xab}$ Karp reductions are just called Karp reductions.

A Karp reduction provides a Cook reduction, since a Turing machine could decide ${L}_{1}$ by calculating $g\beta \x81\u2019(x)$ on any input and determining whether $g\beta \x81\u2019(x)\beta \x88\x88{L}_{2}$. Note that it is a stronger condition than a Cook reduction. For instance, this machine requires only one use of the oracle.

Title | Cook reduction |
---|---|

Canonical name | CookReduction |

Date of creation | 2013-03-22 13:01:41 |

Last modified on | 2013-03-22 13:01:41 |

Owner | Henry (455) |

Last modified by | Henry (455) |

Numerical id | 7 |

Author | Henry (455) |

Entry type | Definition |

Classification | msc 68Q10 |

Classification | msc 68Q05 |

Defines | Karp reduction |