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$ – Suresh Venkat Mar 14 '11 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$ – Tsuyoshi Ito Mar 15 '11 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$ – Antonio E. Porreca Mar 15 '11 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$ – Tsuyoshi Ito Mar 15 '11 at 16:13
  • $\begingroup$ Sorry, apparently I misinterpreted the purpose of your remark. $\endgroup$ – Antonio E. Porreca Mar 15 '11 at 16:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.