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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.