0
$\begingroup$

Suppose $coNP \neq NP$

language B would be called "complete" in $coNP-NP$ if:

  1. $B\in coNP - NP$
  2. $A\in coNP-NP \implies A\leq_pB$

Are there any "complete" languages in $coNP - NP$?

$\endgroup$
3
$\begingroup$

If we are assuming that $coNP≠𝑁𝑃$,

we can conclude that every language that is $co NP$ complete is not in $NP$ (a contradiction to your given assumption).

Thus, every language we already know of that is $coNP$ complete, is complete as well in $coNP -NP$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy