6
$\begingroup$

Let C be a complexity class, and let L be a language such that PC ⊆ PL. 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 PNP ⊆ PUNSAT, 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 PC ⊆ PL 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.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ related: cstheory.stackexchange.com/questions/686/… and cstheory.stackexchange.com/questions/138/… $\endgroup$
    – Suresh Venkat
    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$
    – Tsuyoshi Ito
    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$
    – Antonio E. Porreca
    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$
    – Tsuyoshi Ito
    Mar 15, 2011 at 16:13
  • $\begingroup$ Sorry, apparently I misinterpreted the purpose of your remark. $\endgroup$
    – Antonio E. Porreca
    Mar 15, 2011 at 16:30

0

Reset to default

Your Answer

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