# Cook reduction

Given two (search or decision) problems $\pi_{1}$ and $\pi_{2}$ and a complexity class  $\mathcal{C}$, a $\mathcal{C}$ Cook reduction of $\pi_{1}$ to $\pi_{2}$ is a Turing machine  appropriate for $\mathcal{C}$ which solves $\pi_{1}$ using $\pi_{2}$ as an oracle (the Cook reduction itself is not in $\mathcal{C}$, since it is a Turing machine, not a problem, but it should be the class of bounded Turing machines corresponding to $\mathcal{C}$). The most common type are $\mathcal{P}$ Cook reductions, which are often just called Cook reductions.

If a Cook reduction exists then $\pi_{2}$ is in some sense “at least as hard” as $\pi_{1}$, since a machine which solves $\pi_{2}$ could be used to construct one which solves $\pi_{1}$. When $\mathcal{C}$ is closed under appropriate operations, if $\pi_{2}\in\mathcal{C}$ and $\pi_{1}$ is $\mathcal{C}$-Cook reducible to $\pi_{2}$ then $\pi_{1}\in\mathcal{C}$.

A $\mathcal{C}$ Karp reduction is a special kind of $\mathcal{C}$ Cook reduction for decision problems  $L_{1}$ and $L_{2}$. It is a function $g\in\mathcal{C}$ such that:

 $x\in L_{1}\leftrightarrow g(x)\in L_{2}$

Again, $\mathcal{P}$ 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(x)$ on any input and determining whether $g(x)\in 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 CookReduction 2013-03-22 13:01:41 2013-03-22 13:01:41 Henry (455) Henry (455) 7 Henry (455) Definition msc 68Q10 msc 68Q05 Karp reduction