Cook is faster than Karp: a study of reducibilities in NP
Luc Longpré, P. Young · 1988
It is unknown whether Cook reducibility of a set A to a set B (i.e. reduction of A to B by a Turing machine operating in polynomial time with free procedural calls to an algorithm for B), is more general than Karp reducibility (i.e. reduction of A to B by a function computable in polynomial time) on sets in NP. While it is conjectured that Cook reducibility is indeed a more general notion than Karp reducibility on sets in NP, proving this would imply that P is not equal to NP. More tractable subcases of the problem are investigated, proving, for example, that Cook reducibility is much faster than Karp reducibility on some classes of NP-complete sets.>