0
$\begingroup$

The problem in the title is to be proven, and while proving $\mathrm{coNP}\subset\mathrm{NP}$ is rather clear given the assumptions (see below), I fail to see a way to prove $\mathrm{NP}\subset\mathrm{coNP}$.

My main idea is to prove that $L$ is also $\mathrm{NP}$-complete (or rather $\mathrm{NP}$-hard, as it is in $\mathrm{NP}$), but I don't really see a possibility to prove this, as it is not sufficient that a subset of $\mathrm{NP}$ is reducible to $L$; thus I would be very thankful for some idea for a proof.

Addendum 1:

I am aware of if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$, but in this source only the obvious implication is proven.

Addendum 2 - My proof of the first subset-relation:

All languages $K\in\mathrm{coNP}$ are reducible to the $\mathrm{coNP}$-complete language $L$, thus if $L\in\mathrm{NP}$ every $K$ is reducible to a language in $\mathrm{NP}$ and the implication $K\in\mathrm{coNP}\Rightarrow K\in\mathrm{NP}$, and thus $\mathrm{coNP}\subset\mathrm{NP}$, holds.

$\endgroup$
1
$\begingroup$

$\newcommand{\co}{\mathsf{co}\text{-}}$

Let $A\subseteq \Sigma^*$ be some class of languages. Saying $\co{A}\subseteq A$ means that $A$ is closed under complement, and this is equivalent to $\co{A}=A$.

To show the other direction, $A\subseteq \co{A}$, let $L\in A$ be some language in the class $A$. $\overline{L}\in \co{A}$, and since we know $\co{A}\subseteq A$, we have $\overline{L}\in A$, which means $L\in \co{A}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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