1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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, 2019 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, 2019 at 23:17
  • $\begingroup$ @OrMeir Edited to explicitly include both reductions. $\endgroup$
    – Crabzmatic
    Oct 28, 2019 at 20:55

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.