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:
- 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$.
- 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$.
- 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$.
- Nothing can be determined from the data regarding equality or inequality between $P$ and $NP$
- 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.
- There is no connection between language B and language A, so it is disqualified.
- True, B can also belong to CoNPC, and there can be no reduction from CoNPC to A.
- Can't figure out that answer
- It could also be true that they did not talk about it in question.
- Disqualified maybe 2 or 4 are correct
I can not figure out if the answer is 2 or 4.