3
$\begingroup$

I have a question I was unable to do, from a last test I had.

This is the question:

Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$.

Determine which of the following statements is correct:

  1. In this case it is possible to find a language $B$ such that $B \in CoNPC\cap P$, since it follows that $CoNPC\cap P \neq \emptyset $, and therefore $P=NP$.
  2. The existence of the language $A \in CoNP - CoNPC$ assures us that there is at least one $B \in CoNP$ so that $B \nleq _p A $, so if we assume in the negative that $B \in P$, we can have a contradiction to the non-existence of conversion $B \nleq _p A $, because there can always be a conversion from a problem in $P$ to a $CoNP$ problem. That is, $B \in CoNP$ and also $B \notin P$, and therefore $P \neq CoNP$.
  3. Since there is a language $A \in CoNP$ such that $A \notin CoNPC$ derives as $CoNP - CoNPC \neq \emptyset $, therefore any problem $B$ in $CoNP$ can be solved by converting to problem $C\in P$. That is, it follows that $CoNP \subseteq P $. The bride in the other direction we have already seen, so $P = CoNP$.
  4. Nothing can be determined from the data regarding equality or inequality between $P$ and $NP$
  5. None of the above claims are true.

In the question I am told that:

$A \neq \emptyset ,\sum{_{}}^{*}$ and $A \in CoNP - CoNPC$

And according to this you have to choose one of the 5 options.

I understood the question like this: A, it's some language, not empty. Which belongs only to CoNP.

The answer I think is correct is 2.

  1. There is no connection between language B and language A, so it is disqualified.
  2. True, B can also belong to CoNPC, and there can be no reduction from CoNPC to A.
  3. Can't figure out that answer
  4. It could also be true that they did not talk about it in question.
  5. Disqualified maybe 2 or 4 are correct

I can not figure out if the answer is 2 or 4.

$\endgroup$
2
  • $\begingroup$ What is phi supposed to mean? Did you mean $\emptyset$? $\endgroup$
    – idmean
    Jul 23 at 12:27
  • $\begingroup$ Yes, that's what I meant, I'm fixed it now. $\endgroup$
    – dustyeav
    Jul 23 at 12:40
2
+50
$\begingroup$

We start with the assumption that there is a non-trivial language $A$ which is in $\mathrm{coNP}$, but not $\mathrm{coNP}$-complete. We note that it is rather straight-forward to see that if $\mathrm{P} = \mathrm{coNP}$, then every non-trivial language in $\mathrm{coNP}$ is $\mathrm{coNP}$-complete. Conversely, Ladner's theorem states that if $\mathrm{P} \neq \mathrm{coNP}$, then there are even $\mathrm{coNP}$-intermediate languages, i.e. languages in $\mathrm{coNP}$ which are neither $\mathrm{coNP}$-complete nor in $\mathrm{P}$. (This is typically stated for $\mathrm{NP}$ rather than $\mathrm{coNP}$, but by symmetry that doesn't matter.

Thus, we conclude that the assumption we are starting with is equivalent to $\mathrm{P} \neq \mathrm{NP}$.

  1. This is claiming that $\mathrm{P} = \mathrm{NP}$, and our assumption states the opposite.

  2. I find the formulation a bit awkward, but this is true. Note that "$A$ is not $\mathrm{coNP}$-hard" is just saying that there is some language in $\mathrm{coNP}$ not reducible to it.

  3. The therefore in this statement is a complete non-sequiture.

  4. As explained above, the assumption made is equivalent to $\mathrm{P} \neq \mathrm{NP}$, so the claim is false.

$\endgroup$
0
$\begingroup$

It is 2 that is correct. Here is an alternative explanation:

Notice that any language in $P$ has to be $P$-complete. In addition to that, if $P=NP$ then $NPC=P$-complete. Combining both arguments implies that $NP=P=P\text{-complete}=NPC$. Therefore, if $NP\neq NPC$ then $P\neq NP$.

$\endgroup$
1
  • $\begingroup$ Thanks for the help, it is not clear to me how A actually affects the answer, how does $A \in CoNP - CoNPC$ affects? $\endgroup$
    – dustyeav
    Jul 21 at 8:50

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.