Let C be a complexity class, and let L be a language such that PCPL. Then it’s natural (and easy to prove) that L is C-hard with respect to Cook reductions (polytime Turing reductions).

This fact is not (known to be) true for Karp (polytime many-one) reductions: for instance, we have PNPPUNSAT, but UNSAT is not NP-hard under Karp reductions (unless NP = coNP). On the other hand, most of the times we use Karp reductions to order problems by hardness, since they seem to provide a finer structure.

Are there some “natural” or “interesting” sufficient conditions for PCPL to imply that L is C-hard under Karp reductions?

If that implication held for all C and L, then the two notions of reducibility would coincide (see Tsuyoshi Ito’s comment below); I would be interested in knowing about any interesting class of problems where this happens, if any is known.

  • 4
    $\begingroup$ related: cstheory.stackexchange.com/questions/686/… and cstheory.stackexchange.com/questions/138/… $\endgroup$ Mar 14, 2011 at 18:42
  • 4
    $\begingroup$ If C is a class of decision problems and L is a decision problem, P^C⊆P^L is equivalent to C⊆P^L (one direction of the implications follows from C⊆P^C, the other from P^{P^L}=P^L), that is, L being C-complete under polynomial-time Turing reducibility. Therefore, your question is indeed the same as asking for the condition for the completeness under poly-time Turing reducibility and the completeness under poly-time many-one reducibility to coincide. $\endgroup$ Mar 15, 2011 at 14:50
  • $\begingroup$ What you write is certainly true; however, I wasn’t asking for result holding for all C and L; instead, I was wondering about some conditions on C and L implying that L is C hard wrt Karp reductions. According to your observation, I guess my question could be rephrased as “Do Karp and Cook reducibility coincide for some class of languages?”. $\endgroup$ Mar 15, 2011 at 15:59
  • $\begingroup$ What I meant is that you were asking for a condition on C and L such that L being C-complete under poly-time Turing reducibility and L being C-complete under poly-time many-one reducibility are equivalent. And I should have written “hard” instead of “complete”. So we do not have any disagreement on this. $\endgroup$ Mar 15, 2011 at 16:13
  • $\begingroup$ Sorry, apparently I misinterpreted the purpose of your remark. $\endgroup$ Mar 15, 2011 at 16:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.