<p>Under Karp reductions, the answer is exactly <span class="math-container">$\mathbf{NP}$</span>: it is not hard to see that if a language is Karp-reducible to any <span class="math-container">$\mathbf{NP}$</span>-language, then it is in <span class="math-container">$\mathbf{NP}$</span> too. On the other hand, all of <span class="math-container">$\mathbf{NP}$</span> reduces to <span class="math-container">$\mathbf{NP}$</span>-complete languages by definition.</p>

<p>Under Turing reductions, the answer is the class <span class="math-container">$\mathbf{P}^\mathbf{NP}$</span>: languages that are decidable by a polynomial-time algorithm that has an access to an <span class="math-container">$\mathbf{NP}$</span> oracle. Indeed, a Turing reduction of a language <span class="math-container">$L$</span> to an <span class="math-container">$\mathbf{NP}$</span>-complete language is by definition a polynomial-time algorithm deciding <span class="math-container">$L$</span> with oracle access to <span class="math-container">$\mathbf{NP}$</span>. On the other hand, any such algorithm can be simulated with oracle access to an <span class="math-container">$\mathbf{NP}$</span>-complete language, thus obtaining a Turing reduction.</p>

CC BY-SA 4.0
2019-10-31T18:32:16.547Z
As a non expert: is $\mathbf{P}^\mathbf{NP}$ conjectured to be strictly larger than $\mathbf{NP}$?
cody
CC BY-SA 4.0
2019-11-01T20:31:55.103Z
Yes, it is conjectured to be so.
Or Meir
CC BY-SA 4.0
2019-10-28T23:05:24.700Z
2019-10-28T23:05:24.700Z
Or Meir
<p><strong>NP-complete:</strong> Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in polynomial time - other than languages in NP.</p>

<p><strong>NP-hard:</strong> A problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H. This is reversed reducing, so I'm not sure if this is a good candidate. We don't know whether one can solve NP-hard problem in polynomial time.</p>

<blockquote>
  <p>If P ≠ NP, then NP-hard problems cannot be solved in polynomial time. (NP-hardness wiki)</p>
</blockquote>

<p>So, my question is what class of languages can be transformed to a NP-complete problem in polynomial time using Turing reductions and/or many-to-one reductions.</p>

CC BY-SA 4.0
2019-10-27T16:16:05.540Z
There are several kinds of reductions, e.g., Turing reductions (a.k.a. Cook reductions) and Karp reductions (a.k.a. many-to-one reductions). Which kind of reduction do you have in mind? Also, when you ask "what kind of languages", what kind of answer are you looking for? Examples? A complexity class? A different characterization?
Or Meir
CC BY-SA 4.0
2019-10-27T23:17:25.830Z
For an explicit example of why the above matters, it is known that $$\mathsf{NP} = \mathsf{co-NP}$$ under Turing reductions, but this is open under Karp reductions (and actually not thought to be true). Depending on your notion of reduction you therefore get $$\mathsf{coNP}$$ as an example in the positive or negative case.
Mark Schultz-Wu
CC BY-SA 4.0
2019-10-28T20:55:27.000Z
@OrMeir Edited to explicitly include both reductions.
Crabzmatic
<np-hardness><sat><reductions><np-complete>
What languages can be reduced to a NP-complete problem in polynomial time
Crabzmatic
# What languages can be reduced to a NP-complete problem in polynomial time

(Asked by: username_0 on 2019-10-27)

**NP-complete:** Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in polynomial time - other than languages in NP.

**NP-hard:** A problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H. This is reversed reducing, so I'm not sure if this is a good candidate. We don't know whether one can solve NP-hard problem in polynomial time.

> If P ≠ NP, then NP-hard problems cannot be solved in polynomial time. (NP-hardness wiki)

So, my question is what class of languages can be transformed to a NP-complete problem in polynomial time using Turing reductions and/or many-to-one reductions.

**Tags:** np-hardness, sat, reductions, np-complete
> **Comments:**
> **username_1**: There are several kinds of reductions, e.g., Turing reductions (a.k.a. Cook reductions) and Karp reductions (a.k.a. many-to-one reductions). Which kind of reduction do you have in mind? Also, when you ask "what kind of languages", what kind of answer are you looking for? Examples? A complexity class? A different characterization?  
> **username_2**: For an explicit example of why the above matters, it is known that $$\mathsf{NP} = \mathsf{co-NP}$$ under Turing reductions, but this is open under Karp reductions (and actually not thought to be true). Depending on your notion of reduction you therefore get $$\mathsf{coNP}$$ as an example in the positive or negative case.  
> **username_0**: @OrMeir Edited to explicitly include both reductions.  

---

## 1 answers

### Answer by username_1 on 2019-10-28. Score: 3 | Accepted answer

Under Karp reductions, the answer is exactly $\mathbf{NP}$: it is not hard to see that if a language is Karp-reducible to any $\mathbf{NP}$-language, then it is in $\mathbf{NP}$ too. On the other hand, all of $\mathbf{NP}$ reduces to $\mathbf{NP}$-complete languages by definition.

Under Turing reductions, the answer is the class $\mathbf{P}^\mathbf{NP}$: languages that are decidable by a polynomial-time algorithm that has an access to an $\mathbf{NP}$ oracle. Indeed, a Turing reduction of a language $L$ to an $\mathbf{NP}$-complete language is by definition a polynomial-time algorithm deciding $L$ with oracle access to $\mathbf{NP}$. On the other hand, any such algorithm can be simulated with oracle access to an $\mathbf{NP}$-complete language, thus obtaining a Turing reduction.

> **Comments:**
> **username_3**: As a non expert: is $\mathbf{P}^\mathbf{NP}$ conjectured to be strictly larger than $\mathbf{NP}$?  
> **username_1**: Yes, it is conjectured to be so.  

---

