Given two (search or decision) problems and and a complexity class , a Cook reduction of to is a Turing machine appropriate for which solves using 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 is in some sense “at least as hard” as , since a machine which solves could be used to construct one which solves . When is closed under appropriate operations, if and is -Cook reducible to then .
Again, Karp reductions are just called Karp reductions.
A Karp reduction provides a Cook reduction, since a Turing machine could decide by calculating on any input and determining whether . Note that it is a stronger condition than a Cook reduction. For instance, this machine requires only one use of the oracle.
|Date of creation||2013-03-22 13:01:41|
|Last modified on||2013-03-22 13:01:41|
|Last modified by||Henry (455)|