Cook reducibility is faster than Karp reducibility in NP

摘要

It is unknown whether Cook reducibility of a set A to a set B—that is reduction of A to B via a Turing machine operating in polynomial time with “free” procedural calls to an algorithm for B—is more general than Karp reducibility—that is reduction of A to B via a function computable in polynomial time—on sets in NP. While we conjecture that Cook reducibility is indeed a more general notion than Karp reducibility on sets in NP, proving this would imply that P   NP. Here we investigate more tractable subcases of the problem. For example, we prove that Cook reducibility is much faster than Karp reducibility on some classes of NP-complete sets. We also prove that for some classes of NP-complete sets Cook reductions between members of the classes can be both linearly fast and “linearly honest” while any Karp reduction must be highly “dishonest.”