# 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 NP$$

Suppose that $$A\notin CoNP$$. determine which of the claims is correct:

1. $$P=CoNP$$
2. $$P=NP$$
3. $$P\neq NP$$
4. $$NP \cap CoNP = \phi$$

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 NP and it cannot be in P, because it is not in CoNP, and CoNP itself is in 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.
– dust
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

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}$$.

$$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
– dust
Jul 21, 2021 at 9:04

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