# Relationship between NP and CoNP

I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question

This is the question

Will be $$A\in \mathbf{NP}$$

Suppose that $$A\notin \mathbf{coNP}$$. determine which of the claims is correct:

1. $$\mathbf{P}=\mathbf{coNP}$$
2. $$\mathbf{P}=\mathbf{NP}$$
3. $$\mathbf{P}\neq \mathbf{NP}$$
4. $$\mathbf{NP} \cap \mathbf{coNP} = \varnothing$$

According to the data in the question, you need to choose the correct answer from the 4 possible answers.

I do not understand if there is any connection at all between the language A, and the answers themselves.

What I think is that A must only be in $$\mathbf{NP}$$ and it cannot be in $$\mathbf{P}$$, because it is not in $$\mathbf{coNP}$$, and $$\mathbf{coNP}$$ itself is in $$\mathbf{P}$$.

But I do not find an answer that can fit it, maybe 3 is correct, but it has nothing to do with the question at all, it is always true.

• it is incorrect to say that $coNP\subseteq P$. If this were true then $P=NP$, and we don't know that. Jul 21, 2021 at 8:24
• Thanks, if a problem is in $coNP$, it does not have to be in $P$ too? Or it can be but not necessarily.
– hch
Jul 21, 2021 at 8:32
• Not necessarily. Its an open problem. Knowing whether $coNP\subseteq P$ or $coNP \neq P$ is equivalent to knowing whether $P=NP$ or $P\neq NP$. Jul 21, 2021 at 8:37

$$P$$ is closed under complement. The rest is up to you.

• Thanks, if I understood you correctly, actually, P = COP, and by the question $A\in NP$ and $A\notin CoNP$, therefore $CoNP \neq NP$ and get that $CoP \neq P$ , but I do not see an answer to it
– hch
Jul 21, 2021 at 9:04

The correct answer is no. 3.

Suppose $$A \in \text{NP}$$ and $$A \notin \text{co-NP}$$. Clearly this shows $$\text{NP} \neq \text{coNP}$$, but that's not a possible choice for this question.

Observe that complement of the machine output can be trivially implemented in a deterministic polynomial machine. That is to say, $$\text{P} = \text{co-P}$$. Thus, if $$\text{P} = \text{NP}$$, then $$P = \text{co-NP}$$, which together imply $$\text{NP} = \text{co-NP}$$. This cannot be the case by assumption, so $$\text{P} \neq \text{NP}$$.

1+2 are not proven true and false, considered to be extremely hard to be proven either way, and most people assume they are false. That obviously answers 3.

4: P is a subset of both NP and co-NP, and since P is not empty, 4 is false.

Language A is indeed irrelevant. If the question had said "assume A in co-NP" that would have shown much more trivially that 4 is false, but it's false anyway.

• The language $A$ is not irrelevant. If there is a language $A\in NP$ but $A\not\in coNP$, as the question assumes, then it follows that $P\ne NP$, so 3 is the only correct statement of the four. Aug 20, 2021 at 18:52