# Oracle complexity classes and hardness under different notions of reduction

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.

• – Suresh Venkat Mar 14 '11 at 18:42
• 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. – Tsuyoshi Ito Mar 15 '11 at 14:50
• 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?”. – Antonio E. Porreca Mar 15 '11 at 15:59
• 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. – Tsuyoshi Ito Mar 15 '11 at 16:13
• Sorry, apparently I misinterpreted the purpose of your remark. – Antonio E. Porreca Mar 15 '11 at 16:30