I searched the internet for a proof of the statement: If a $coNP$-hard problem is in $NP$, then $NP=coNP$ (NP-hard problem is in coNP). I found a proof sketch here (page 3 in the pdf, slide 341) and I wanted to make sure I understand it correctly. The proof-sketch gives a proof for one direction (if a $coNP$-hard problem is in $NP$, then $coNP \subseteq NP$), but leaves the other direction ($NP \subseteq coNP$) to the reader.

Here is the proof for both directions:

$coNP \subseteq NP$ (taken from the slides)

  • Let $L \in NP$ be coNP-hard.
  • Let NTM $M$ decide $L$.
  • Since $L$ coNP-hard, for any $L' \in coNP$ there is a reduction $R$ from $L'$ to $L$.
  • But then $L' \in NP$ as it is decided by NTM $M(R(x))$.
  • Thus, $coNP \subseteq NP$

Now my attempt at the other direction ($NP \subseteq coNP$):

  • Let $L' \in NP$ and its complement $\bar{L'} \in coNP$.
  • Thus there is a reduction from $\bar{L'}$ to $L$.
  • Thus $\bar{L'} \in NP$, as it is decided by NTM $M(R(x))$.
  • But then $L' \in coNP$
  • Hence, $NP \subseteq coNP$

Is this correct?

For the statement that if an $NP$-hard problem is in $coNP$, then $NP=coNP$, the slides just state that the proof works similarly. However, I am struggling to work out the details of the proof. In particular, how can I leverage the reduction to choose that a language which is NP/coNP is also in coNP/NP respectively?


closed as unclear what you're asking by vonbrand, Evil, David Richerby, Yuval Filmus, Discrete lizard Sep 12 at 17:43

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – dkaeae Aug 12 at 13:09