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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Or Meir Oct 27 '19 at 16:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Oct 27 '19 at 23:17
  • $\begingroup$ @OrMeir Edited to explicitly include both reductions. $\endgroup$ – Crabzmatic Oct 28 '19 at 20:55

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.

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

Your Answer

