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 .

A Karp reduction is a special kind of Cook reduction for decision problems and . It is a function such that:

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.