Cook reduction


Given two (search or decision) problems Ο€1 and Ο€2 and a complexity classPlanetmathPlanetmath π’ž, a π’ž Cook reduction of Ο€1 to Ο€2 is a Turing machineMathworldPlanetmath appropriate for π’ž which solves Ο€1 using Ο€2 as an oracle (the Cook reduction itself is not in π’ž, since it is a Turing machine, not a problem, but it should be the class of bounded Turing machines corresponding to π’ž). The most common type are 𝒫 Cook reductions, which are often just called Cook reductions.

If a Cook reduction exists then Ο€2 is in some sense β€œat least as hard” as Ο€1, since a machine which solves Ο€2 could be used to construct one which solves Ο€1. When π’ž is closed under appropriate operations, if Ο€2βˆˆπ’ž and Ο€1 is π’ž-Cook reducible to Ο€2 then Ο€1βˆˆπ’ž.

A π’ž Karp reduction is a special kind of π’ž Cook reduction for decision problemsMathworldPlanetmath L1 and L2. It is a function gβˆˆπ’ž such that:

x∈L1↔g⁒(x)∈L2

Again, 𝒫 Karp reductions are just called Karp reductions.

A Karp reduction provides a Cook reduction, since a Turing machine could decide L1 by calculating g⁒(x) on any input and determining whether g⁒(x)∈L2. 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