<p>Let <b>C</b> be a complexity class, and let <i>L</i> be a language such that <b>P</b><sup><b>C</b></sup> &sube; <b>P</b><sup><i>L</i></sup>. Then it’s natural (and easy to prove) that <i>L</i> is <b>C</b>-hard with respect to Cook reductions (polytime Turing reductions).</p>

<p>This fact is not (known to be) true for <i>Karp</i> (polytime many-one) reductions: for instance, we have <b>P</b><sup><b>NP</b></sup> &sube; <b>P</b><sup>UNSAT</sup>, but UNSAT is not <b>NP</b>-hard under Karp reductions (unless <b>NP</b> = <b>coNP</b>). 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.</p>

<blockquote>
  <p>Are there some “natural” or “interesting” sufficient conditions for <b>P</b><sup><b>C</b></sup> &sube; <b>P</b><sup><i>L</i></sup> to imply that <i>L</i> is <b>C</b>-hard under Karp reductions?</p>
</blockquote>

<p>If that implication held for all <b>C</b> and <i>L</i>, 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.</p>

CC BY-SA 2.5
2011-03-15T14:50:44.547Z
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
CC BY-SA 2.5
2011-03-15T15:59:53.893Z
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
CC BY-SA 2.5
2011-03-15T16:13:33.047Z
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
CC BY-SA 2.5
2011-03-15T16:30:09.437Z
Sorry, apparently I misinterpreted the purpose of your remark.
Antonio E. Porreca
CC BY-SA 2.5
2011-03-14T18:42:54.220Z
related: http://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc and http://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc
Suresh Venkat
<cc.complexity-theory><reductions><oracles>
Oracle complexity classes and hardness under different notions of reduction
Antonio E. Porreca
# Oracle complexity classes and hardness under different notions of reduction

(Asked by: username_0 on 2011-03-14)

Let **C** be a complexity class, and let *L* be a language such that **P****C** ⊆ **P***L*. 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 **P****NP** ⊆ **P**UNSAT, 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 **P****C** ⊆ **P***L* 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.

**Tags:** cc.complexity-theory, reductions, oracles
> **Comments:**
> **username_2**: related: http://cstheory.stackexchange.com/questions/686/do-many-one-reductions-and-turing-reductions-define-the-same-class-npc and http://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc  
> **username_1**: 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.  
> **username_0**: 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?”.  
> **username_1**: 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.  
> **username_0**: Sorry, apparently I misinterpreted the purpose of your remark.  

---

## 0 answers

