1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ it is incorrect to say that $coNP\subseteq P$. If this were true then $P=NP$, and we don't know that. $\endgroup$
    – nir shahar
    Jul 21, 2021 at 8:24
  • $\begingroup$ Thanks, if a problem is in $coNP$, it does not have to be in $P$ too? Or it can be but not necessarily. $\endgroup$
    – hch
    Jul 21, 2021 at 8:32
  • $\begingroup$ 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$. $\endgroup$
    – nir shahar
    Jul 21, 2021 at 8:37

3 Answers 3

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – hch
    Jul 21, 2021 at 9:04
1
$\begingroup$

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

Improve this answer
$\endgroup$
-2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Lieuwe Vinkhuijzen
    Aug 20, 2021 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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