#StackBounty: #complexity-theory #computability #np-complete #reductions #np Reduction with CoNP and CoNPC

Bounty: 50

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 varnothing ,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 CoNPCcap P$, since it follows that $CoNPCcap P neq varnothing $, 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 varnothing $, therefore any problem $B$ in $CoNP$ can be solved by converting to problem $Cin 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 varnothing ,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.

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.