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.