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