# What languages can be reduced to a NP-complete problem in polynomial time

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.

• 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? Oct 27 '19 at 16:16
• 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
Oct 27 '19 at 23:17
• @OrMeir Edited to explicitly include both reductions. Oct 28 '19 at 20:55

## 1 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.

• As a non expert: is $\mathbf{P}^\mathbf{NP}$ conjectured to be strictly larger than $\mathbf{NP}$?
– cody
Oct 31 '19 at 18:32
• Yes, it is conjectured to be so. Nov 1 '19 at 20:31